문제 출처
https://www.acmicpc.net/problem/16987
정답 풀이
완전 탐색을 이용한다.
정답 코드
//계란으로 계란 치기
//-각 계란 내구도, 무게
//-상대 계란의 무게만큼 계란의 내구도가 깍임
//-계란 0이하 깨짐
//일렬 계란, 차례로 들어, 한번씩 다른 계란 쳐 => 최대한 많은 계란 깨기
let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const n = Number(input.shift());
let egg = input.map(el => el.split(' ').map(v => +v));
function solution(n,egg){
let max = 0
function dfs(L){
if(L === n){
let result = check()
max = Math.max(max, result)
return;
}
if(egg[L][0] <= 0){
dfs(L+1);
return;
}
let isSmashed = false;
for(let i=0; i<n; i++){
if(L !== i && egg[i][0] >0){
isSmashed = true;
egg[L][0] -= egg[i][1]
egg[i][0] -= egg[L][1]
dfs(L+1)
egg[L][0] += egg[i][1]
egg[i][0] += egg[L][1]
}
}
if(!isSmashed){
dfs(L+1)
}
}
function check(){
let cnt = 0
egg.forEach(el => {
if(el[0] <= 0) cnt++
})
return cnt;
}
dfs(0)
return max;
}
//완탐
//해당 이거로 다음 것들 중이랑 해서 깨는거
//해당 계란 상태 나타내는 배열
//L = 계란 n
//해당 계란이 깨져있다면 L+1
console.log(solution(n, egg))
추가 설명
ChatGPT의 말:
좋은 질문입니다! 재귀 호출(dfs)에서 "원상 복구"를 해줘야 하는 이유는 모든 경우의 수를 탐색하는 과정에서 상태를 되돌리기 위해서입니다. 한 번 깬 계란의 내구도를 복구하지 않으면, 그 이후의 탐색에서 이전 탐색의 영향을 받게 되어 잘못된 결과를 도출할 수 있기 때문입니다. 이를 좀 더 구체적으로 설명하겠습니다.
재귀 호출에서 상태 복구의 필요성
dfs(L) 함수는 계란을 하나씩 선택해서 다른 계란을 칠 때마다 상태 변화가 발생합니다. 즉, 현재 계란의 내구도가 감소하고 상대 계란의 내구도도 감소합니다. 이 상태 변화는 현재 탐색 경로에서만 유효해야 합니다. 하지만 JavaScript의 배열(또는 객체)은 참조 타입이므로, 상태 변화가 공유된다는 점이 중요한데, 만약 상태를 복구하지 않으면 이전 탐색 경로의 영향을 계속 받게 됩니다.
왜 상태 복구가 필요한가?
예를 들어, 계란이 두 개 있다고 가정해 봅시다.
- 첫 번째 계란(A)과 두 번째 계란(B)이 있습니다.
- 첫 번째 계란(A)을 들어 두 번째 계란(B)을 칩니다.
- 이때 A의 내구도와 B의 내구도가 변합니다.
- 이후의 탐색에서 A와 B의 내구도가 변화된 상태로 유지된 채 다른 계란을 칠 수 있습니다.
- 이때, 두 계란의 내구도가 이미 감소된 상태에서 다음 경우를 고려하게 됩니다.
- 문제는, 다른 경우의 수를 탐색할 때, 초기 상태에서 출발해야 하는데, 내구도가 감소된 상태로 탐색을 계속하면 잘못된 결과가 나옵니다.
- 예를 들어, A와 B 모두 내구도가 0 이하가 되었을 경우, 이후 탐색에서는 A나 B를 다시 사용할 수 없어야 하는데, 원상 복구를 하지 않으면 이전 탐색에서 감소된 내구도를 그대로 유지한 상태로 다음 경로를 고려하게 됩니다.
따라서 원상 복구를 해주어야만, 한 경로가 끝났을 때(즉, 재귀 호출이 완료되었을 때) 이전 상태로 돌아가서 다른 경우의 수를 정확하게 탐색할 수 있습니다.
재귀 호출 후 상태 복구가 없으면 발생할 수 있는 문제 예시
function dfs(L) {
// 예: A가 B를 칠 때 내구도가 변경됨
egg[L][0] -= egg[i][1];
egg[i][0] -= egg[L][1];
dfs(L + 1);
// 만약 여기서 원상 복구를 하지 않으면
// 이후의 탐색에서 계란 상태가 이미 깎인 상태로 유지됨
}
만약 상태 복구를 하지 않고 재귀 호출(dfs)을 한다면, 다음번 탐색(dfs(L + 1))은 이미 내구도가 깎인 계란 상태에서 시작하게 됩니다. 이는 이전 탐색의 영향을 받는 잘못된 탐색을 하게 만드는 원인이 됩니다.
따라서 재귀 호출 후에는 원상 복구를 해줘야 다음 경로를 탐색할 때 처음의 상태에서 시작할 수 있게 됩니다. 즉, 이전에 계란을 쳤던 기록을 지워주고 새로운 경우의 수를 고려할 때 초기 상태에서 올바르게 출발할 수 있도록 해야 합니다.
결론
재귀 탐색에서 상태를 복구하지 않으면 잘못된 탐색이 이루어질 가능성이 크기 때문에, 재귀 호출 후 계란의 내구도를 원래대로 복구해 주어야 다른 경로를 탐색할 때 올바른 상태에서 출발할 수 있습니다.
02. 전에 dfs 문제를 풀면서 저절로 빼진 경우가 있었떤 것 같아 그건 어떤 경우야?
ChatGPT의 말:
DFS(깊이 우선 탐색)에서 "저절로 상태가 원래대로 돌아가는" 것처럼 보이는 경우는, 함수 호출이 값을 직접 복사해서 전달하는 방식이나 상태 변화를 재귀 호출 내부에서 일시적으로 처리하는 방식일 때 발생할 수 있습니다. 특히 값을 복사하거나 로컬 변수를 사용할 경우에는 재귀 호출이 끝나면 자동으로 해당 스코프가 끝나면서 값이 사라지기 때문에 상태를 복원할 필요가 없는 경우가 생깁니다.
상태 복구가 필요 없을 때 (자동 복원되는 경우)
- 값을 복사해서 사용하는 경우:
- 만약 함수가 배열이나 객체와 같은 참조 타입이 아니라 값 타입을 복사해서 사용한다면, 재귀 호출이 끝날 때마다 그 값이 원래 상태로 돌아옵니다. 즉, 재귀 함수 내에서 값을 직접 변경해도, 재귀가 끝나면 그 값은 영향을 받지 않습니다.
function dfs(L, status) {
// status는 새로 복사된 값이므로 재귀 호출 이후 상태가 자동으로 복구
let newStatus = [...status]; // 배열을 새롭게 복사
newStatus[L] -= 1; // 값 수정
if (L === n) {
return;
}
dfs(L + 1, newStatus); // 재귀 호출
}이 경우 status 배열을 복사해서 사용하고 있으므로, newStatus가 변하더라도 원래 status 배열은 변경되지 않습니다. 그래서 재귀 호출이 끝나면 별도의 상태 복구가 필요 없습니다.
2. 상태가 함수 내부에서만 임시로 변경될 때:
- 재귀 함수 내부에서 상태가 단순히 임시 변수로 처리되는 경우라면, 그 변수는 재귀 호출이 끝나면 자동으로 사라지거나 초기화됩니다. 즉, 스택 프레임이 종료되면서 상태가 자동으로 복구되는 셈입니다.
예를 들어, 이런 경우입니다:
function dfs(L, count) {
count++; // count는 함수 호출마다 새로운 값으로 처리됨
if (L === n) {
return;
}
dfs(L + 1, count); // 재귀 호출 시, 값이 복사됨
}
여기서 count는 숫자 값이기 때문에 재귀 호출 시 새로운 값이 함수로 전달됩니다. 그래서 상태를 따로 복구하지 않아도 재귀가 끝나면 자동으로 이전 count 값으로 돌아갑니다.
상태 복구가 필요한 경우
반면, 배열이나 객체 같은 참조 타입을 수정하는 경우에는, 재귀 호출 과정에서 모든 함수 호출이 같은 참조를 공유하기 때문에 상태가 바뀌면 영구적으로 그 변경이 유지됩니다. 이럴 때는 수동으로 상태를 복구해야 합니다. 예를 들어, 계란 내구도 문제에서 배열을 복사하지 않고 그대로 사용할 경우, 상태가 공유되기 때문에 상태 복구가 필요합니다.
function dfs(L, eggStatus) {
// eggStatus는 참조 타입이므로 재귀가 끝나도 변한 값이 유지됨
eggStatus[L] -= 1; // 값 수정 (참조를 통해 원본도 바뀜)
if (L === n) {
return;
}
dfs(L + 1, eggStatus); // 재귀 호출 후에도 eggStatus는 그대로 유지됨
// 상태를 복구하지 않으면 여기서 eggStatus는 변경된 상태 그대로임
}여기서 상태 복구가 없으면, 재귀 호출 후에도 eggStatus는 변경된 상태로 남게 됩니다. 이를 막기 위해 상태 복구가 필요합니다.
결론
상태 복구가 필요 없는 경우는 주로:
- 값을 복사해서 함수에 전달하거나,
- 임시 값을 로컬 변수로 사용해서 재귀 호출하는 경우입니다.
반면, 상태 복구가 필요한 경우는:
- **참조 타입(배열, 객체 등)**이 함수 호출 간에 공유되어 상태가 영구적으로 변경되는 경우입니다.
DFS에서 상태를 복구해야 할지 여부는 참조 타입을 사용하는지, 값 타입을 사용하는지에 따라 다릅니다.
나의 말:
ChatGPT의 말:
이 경우에 return을 하지 않으면, 불필요한 코드가 실행될 수 있고, 의도하지 않은 동작이 발생할 수 있습니다. 아래에서 그 이유를 설명하겠습니다.
이유 1: 불필요한 코드 실행 방지
현재 dfs(L + 1)을 호출한 후 return이 없으면, 재귀 호출 이후에도 아래에 있는 다른 코드가 실행될 수 있습니다. 특히 재귀 함수에서는 특정 조건을 만족하면 그 지점에서 바로 함수를 종료해야 할 때가 많습니다. 만약 return을 생략한다면 함수가 끝나지 않고, 그 이후의 코드를 계속 실행하게 됩니다.
if (egg[L][0] <= 0) {
dfs(L + 1); // 현재 계란이 깨져 있으므로 다음 계란으로 넘어감
// return이 없으면 이후 코드가 계속 실행됨
}
// 아래 코드가 계속 실행됨위 코드에서 egg[L][0] <= 0인 경우, 즉 현재 계란이 이미 깨져 있을 때는 그 이후의 로직을 수행할 필요가 없습니다. 그러나 return이 없으면, 그 상태에서 계속 다음 코드가 실행되게 됩니다. 이 경우, 이미 깨진 계란으로 다른 계란을 치려고 시도하거나 불필요한 연산이 발생할 수 있습니다.
이유 2: 논리적인 흐름 보장
재귀 호출에서는 특정 조건을 만족했을 때 그 즉시 함수를 종료하는 것이 중요한데, return을 하지 않으면 다음 로직이 실행되므로 의도한 대로 코드가 작동하지 않을 가능성이 있습니다.
예를 들어, 계란이 이미 깨진 상태라면 그 계란은 더 이상 다른 계란과 상호작용할 필요가 없으므로, 함수는 즉시 종료되어야 합니다. return을 생략하게 되면 egg[L][0] <= 0인 계란도 이후의 타격 로직에 들어갈 수 있게 됩니다. 이로 인해 잘못된 동작이 발생할 수 있습니다.
예시: return이 없을 때 발생할 수 있는 문제
if (egg[L][0] <= 0) {
dfs(L + 1); // 다음 계란으로 넘어감
// return이 없으므로 아래 코드가 실행됨
}
for (let i = 0; i < n; i++) {
if (i !== L && egg[i][0] > 0) {
egg[L][0] -= egg[i][1];
egg[i][0] -= egg[L][1];
dfs(L + 1);
egg[L][0] += egg[i][1];
egg[i][0] += egg[L][1];
}
}
여기서 return이 없으면, 이미 깨진 계란(즉 egg[L][0] <= 0인 경우)에서도 for 루프가 실행됩니다. 이 경우, 깨진 계란으로 다른 계란을 치려는 시도를 하게 되어 논리적으로 잘못된 상태가 될 수 있습니다.
결론
return은 함수가 불필요한 코드를 실행하지 않도록 하고, 논리적으로 조건을 만족한 경우 함수가 정상적으로 종료되도록 돕습니다. 이 경우에는 이미 계란이 깨졌을 때, 그 계란을 더 이상 처리할 필요가 없으므로 즉시 함수를 종료하는 것이 적절하며, 이를 위해 return이 필요합니다.
따라서 return을 생략하면, 깨진 계란도 이후 코드에 의해서 불필요한 처리를 하게 되어 잘못된 결과를 초래할 수 있습니다.
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 13325: 이진트리 - javascript(트리) (0) | 2024.09.30 |
|---|---|
| 백준 11066: 파일 합치기 - javascript(dp) (0) | 2024.09.30 |
| 프로그래머스 : 소수 찾기 - javascript(완전탐색, 소수 판별) (0) | 2024.09.29 |
| 백준 4256 : 트리 - javascript(트리) (1) | 2024.09.28 |
| 백준 2225 : 합분해 - javascript(dp) (1) | 2024.09.28 |