문제 출처
나의 풀이 (실패)
전위/중위/후위에 꽂혀서 문제를 너무 어렵게 접근했다.
부모 노드와 자식 노드의 관계를 어떻게 맺어야 하는지에서 막혔다.
단순히 dfs를 진행하면 되는 문제였다.
정확히 말하자면, dfs에 대한 이해가 많이 부족했다.
일단 노드에 방문해서 연산을 진행하고
다음에 방문할 노드를 어떻게 결정할지를 고민했어야 했다.
다른 풀이
단순하게 현재 노드에서 양과 늑대의 비율을 계산해주고
다음에 갈 수 있는 노드 경우의 수를 찾아서 재귀를 진행해주면 된다.
- 그래프를 생성해 정보를 저장해둔다.
- 특정 노드에 진입하면 양과 늑대의 비율을 계산한다.
- 2번을 통과했다면 현재 노드에서 갈 수 있는 다음 노드들을 계산해서 이 노드 목록을 가지고 재귀를 진행하면 된다.
function solution(info, edges) {
let answer = 1
const length = info.length
// 1. 그래프 생성
const graph = Array.from({length}, () => [])
for(let i = 0; i < edges.length; i++){
const [from, to] = edges[i]
graph[from].push(to)
}
const dfs = (current, nextNodes) => {
let [currentNode, sheep, wolves] = current
const newNextNodes = [...nextNodes]
const index = newNextNodes.indexOf(currentNode)
// 2. 정답 도출
sheep += !info[currentNode]
wolves += info[currentNode]
answer = Math.max(answer, sheep)
if(sheep === wolves) return
// 3. 다음 방문 노드 탐색
if(graph[currentNode].length){
newNextNodes.push(...graph[currentNode])
}
newNextNodes.splice(index, 1)
for(const nextNode of newNextNodes){
dfs([nextNode, sheep, wolves], newNextNodes)
}
}
dfs([0, 0, 0], [0])
return answer
}
console.log(
solution(
[0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1],
[
[0, 1],
[1, 2],
[1, 4],
[0, 8],
[8, 7],
[9, 10],
[9, 11],
[4, 3],
[6, 5],
[4, 6],
[8, 9],
]
)
); // 5이 풀이에서는 트리를 단방향으로 생성했다.
문제에서 내가 왔던 노드로 다시 돌아갈 가능성이 있다면 단방향보다 양방향으로 그래프를 생성해주는 게 좋다.
// 단방향
const [from, to] = edges[i]
graph[from].push(to)
// 양방향
const [from, to] = edges[i]
graph[from].push(to)
graph[to].push(from)다른 풀이 2
단순 백트래킹으로 문제가 해결되지만,
크기가 커지면 이미 방문한 노드를 또 방문하는 중복 문제가 발생할 수 있다.
이때는 dp를 사용해야 한다.
https://blog.encrypted.gg/1029
-
피보나치 함수를 재귀로 구현할 때 상태의 중복이 발생하는 문제를 메모이제이션으로 해결한 것처럼 비트마스킹을 이용해 vis[..]에 특정 상태를 방문했는지 저장.
-
예를 들어 [0,1,7,8,9]번 정점을 방문한 상태는 1110000011 = 899로 나타내어 vis[899]를 1로 만든다.
1110000011을 2^n으로 표현하면 다음과 같다.
(1110000011)₂ = (1 × 2⁹) + (1 × 2⁸) + (1 × 2⁷) + (0 × 2⁶) + (0 × 2⁵) + (0 × 2⁴) + (0 × 2³) + (0 × 2²) + (1 × 2¹) + (1 × 2⁰) = (899)₁₀
- 총 2^n개의 상태에 대해 모든 상태를 방문하면 된다. 이때는 bfs, dfs 어느 것을 사용하든 상관없다.
function solution(info, edges) {
let ans = 1
let n = info.length
let vis = new Array(1<<17) // vis[x] : 상태 x를 방문 했는지 (info.length가 최대 17이므로)
let left = new Array(20) // 왼쪽 자식
let right = new Array(20) // 오른쪽 자식
let value = new Array(20) // 양/늑대 값
for(let i=0; i<n; i++) left[i] = -1
for(let i=0; i<n; i++) right[i] = -1
for(let i=0; i<n; i++) value[i] = info[i]
for(let i=0; i<n-1; i++){
const [parent, child] = edges[i] // [부모, 자식]
if(left[parent] == -1) left[parent] = child
else right[parent] = child
}
const solve = (state) => {
if(vis[state]) return
vis[state] = 1
let wolf = 0 // wolf : 늑대 수
let num = 0 // num : 전체 정점 수
for(let i=0; i<n; i++){
console.log(state, i, (1<<i), (state & (1<<i)))
if(state & (1<<i)){
num++
wolf += value[i]
}
}
if(2*wolf >= num) return // 만약 늑대가 절반 이상일 경우 방문 불가능하므로 종료
ans = Math.max(ans, num-wolf) // 현재 state의 양의 수가 ans보다 클 경우 ans 업데이트
for(let i=0; i<n; i++){ // 다음 상태로 넘어가기
console.log(state, i, (1<<i), (state | (1<<i)))
if(!(state & (1<<i))) continue // i번째 비트가 꺼져 있는 경우, 해당 정점이 없으니 패스
if(left[i] != -1) solve(state | (1<<left[i])) // 현재 보고 있는 i번째 정점의 left가 있으면
if(right[i] != -1) solve(state | (1<<right[i])) // 현재 보고 있는 i번째 정점의 right가 있으면
}
}
solve(1) // 0번 노드만 포함된 상태에서 dfs 시작
return ans
}AND 비트 연산자(&)는 두 개의 피연산자의 각 자리마다 대응하는 비트가 모두 1일 경우에만 1을 반환한다.
예를 들어
. 9 (base 10) = 00000000000000000000000000001001 (base 2)
14 (base 10) = 00000000000000000000000000001110 (base 2)
--------------------------------
14 & 9 (base 10) = 00000000000000000000000000001000 (base 2) = 8 (base 10)아래 코드를 보면 이해하겠지만 1<<i는 2^i를 의미한다.
state & (1<<i) 값이 truthy일 때만 정점을 추가하고, 거기에 value[i]를 추가해서 늑대의 개수만 고려해준다.
양의 숫자보다 늑대의 숫자가 커지면 안 되므로, 늑대의 숫자만 고려하면 된다.
늑대의 숫자만 고려해서(늑대면 1이므로 값이 증가할 것이고, 0이면 양인데, 어쨌든 늑대의 값은 증가하지 않는다) 전체 정점에서 늑대의 숫자를 빼면 양의 숫자도 자연스럽게 도출하면 된다.
for(let i=0; i<n; i++){
console.log(state, i, (1<<i), state & (1<<i))
if(state & (1<<i)){
num++
wolf += value[i]
}
}위 코드에서 예를 들어 state가 259일 때를 생각해보면
259를 2진수로 변환하면 100000011이다.
(1 × 2⁸) + (0 × 2⁷) + (0 × 2⁶) + (0 × 2⁵) + (0 × 2⁴) + (0 × 2³) + (0 × 2²) + (1 × 2¹) + (1 × 2⁰)
부분집합으로 표현하면 {0, 1, 8}으로 표현할 수 있다.
이떄 i=0 ~n-1까지의 (1<<i)를 고려해보면 다음과 같다.
i=0, (1<<i)=1 == 0000000001, state & (1<<i)= 1
i=1, (1<<i)=2 == 0000000010, state & (1<<i)= 2
i=2, (1<<i)=4 == 0000000100, state & (1<<i)= 0
i=3, (1<<i)=8 == 0000001000, state & (1<<i)= 0
i=4, (1<<i)=16 == 0000010000, state & (1<<i)= 0
i=5, (1<<i)=32 == 0000100000, state & (1<<i)= 0
i=6, (1<<i)=64 == 0001000000, state & (1<<i)= 0
i=7, (1<<i)=128 == 0010000000, state & (1<<i)= 0
i=8, (1<<i)=256 == 0100000000, state & (1<<i)= 256
i=9, (1<<i)=512 == 1000000000, state & (1<<i)= 0 즉, 부분집합 {0, 1, 8}을 가지는 259가 state일 때
- 부분집합 {0}을 가지는 1과
- 부분집합 {1}을 가지는 2와
- 부분집합 {8}을 가지는 8일 때
truthy 값을 가지게 되고 이때 노드를 추가해 전진할 수 있게 된다.
(바꿔 말하면 259라는 의미는 0,1,8 노드를 거쳐왔다고 볼 수 있다.)
그리고 그럴 때의 그 노드의 값을 value[i]에서 가져와서
늑대의 숫자를 계산한 뒤
늑대의 숫자가 양의 숫자보다 크거나 같아지면 안 된다는 의미를 다르게 접근하면
늑대의 숫자 x 2한 값이 전체 노드의 갯수보다 크거나 같으면 안 된다는 의미로 확장할 수 있다.
그리고 이런 접근 방식을 사용하면 현재 state이 어떤 경로를 거쳐왔는지를 부분집합으로 알아낼 수 있다. 이를 통해 현재 양/늑대의 숫자 비율로 현재 노드가 가능한지 불가능한지 판단할 수 있다.
위에서 & 연산자를 사용해서 현재 state이 가능한 정점인지 판단했다면,
그 다음에는 | 연산자를 사용해서 다음에 갈 수 있는 state를 찾는다.
비트 논리 연산자 OR :| => 비트단위로 OR 연산을 한다.
둘중 하나라도 1이면 결과가 1이다. 둘다 0일때만 결과가 0이다.
for(let i=0; i<n; i++){ // 다음 상태로 넘어가기
console.log(state, i, (1<<i), (state | (1<<i)))
if(!(state & (1<<i))) continue // i번째 비트가 꺼져 있는 경우, 해당 정점이 없으니 패스
if(left[i] != -1) solve(state | (1<<left[i])) // 현재 보고 있는 i번째 정점의 left가 있으면
if(right[i] != -1) solve(state | (1<<right[i])) // 현재 보고 있는 i번째 정점의 right가 있으면
}방문하지 않은 노드에 대해, 또 다시 259로 예를 들면
259를 2진수로 변환하면 100000011이고,
부분집합으로 표현하면 {0,1,8}이다.
i=0, (1<<i)=1 == 0000000001, state | (1<<i)= 259
i=1, (1<<i)=2 == 0000000010, state | (1<<i)= 259
i=2, (1<<i)=4 == 0000000100, state | (1<<i)= 263
i=3, (1<<i)=8 == 0000001000, state | (1<<i)= 267
i=4, (1<<i)=16 == 0000010000, state | (1<<i)= 275
i=5, (1<<i)=32 == 0000100000, state | (1<<i)= 291
i=6, (1<<i)=64 == 0001000000, state | (1<<i)= 323
i=7, (1<<i)=128 == 0010000000, state | (1<<i)= 387
i=8, (1<<i)=256 == 0100000000, state | (1<<i)= 259위 0~8 경우를 부분집합으로 표현하면 다음과 같다.
i=0 => 259 (100000011) => {0,1,8}
i=1 => 259 (100000011) => {0,1,8}
i=2 => 263 (100000111) => {0,1,2,8}
i=3 => 267 (100001011) => {0,1,3,8}
i=4 => 275 (100010011) => {0,1,4,8}
i=5 => 291 (100100011) => {0,1,5,8}
i=6 => 323 (101000011) => {0,1,6,8}
i=7 => 387 (110000011) => {0,1,7,8}
i=1 => 259 (100000011) => {0,1,8}2,3,4,5,6,7번 노드로 이동할 수 있다는 의미를 갖는다.
0,1,8의 경우 이미 거쳐왔던 노드이므로 바로 return 된다.
참고
[2022 KAKAO Blind Recruitment] Q5. 양과 늑대 (C++, Python, Java)
[ 프로그래머스 양과늑대 (Lv3) ] (C++)
연산자(3) : 비트 연산자의 명확한 이해
