[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 양과 늑대

문제를 정리해보자.

 

1. 이진 트리 모양의 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있다. 

2. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다.

3. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 나를 따라온다.

4. 이때, 양의 수보다 늑대의 수가 많아지면 모든 양은 잡아 먹힌다.

 

중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아보자. 

 

---

 

풀이를 생각해보자.

 

 

프로그래머스 예제 2번

 

 

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면

양 5마리, 늑대 3마리가 된다.

여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리로 양이 모두 잡아 먹힌다.

따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리이다.

(프로그래머스 문제에 나오는 설명을 가져왔다.)

 

 

 

수기 작성

 

 

완전 탐색으로 양을 모을 수 있는 모든 경우의 수를 찾아보자.

조건은 양의 수가 늑대의 수보다 많아야 한다.

 

 

1) 0번 노드는 1, 2번 노드로 갈 수 있다.

 

0번 - 1번 (X) : 양 1마리, 늑대 1마리

0번 - 2번 (O) : 양 2마리, 늑대 0마리

 

 

2) 0, 2번 노드는 1, 5, 6번 노드로 갈 수 있다.

 

0번 - 2번 - 1번(O) : 양 2마리, 늑대 1마리

0번 - 2번 - 5번(O) : 양 3마리, 늑대 0마리

0번 - 2번 - 6번(O) : 양 2마리, 늑대 1마리

 

 

3-1) 0, 2, 1번 노드는 3, 4, 5, 6번 노드로 갈 수 있다.

 

3-2) 0, 2, 5번 노드는 1, 6번 노드로 갈 수 있다.

 

3-3) 0, 2, 6번 노드는 1, 9번 노드로 갈 수 있다.

 

 

이렇게 해서 최댓값을 찾으면 된다.

 

---

 

구현해보자

 

BFS로 다음 노드를 추가하고 이동했다.

그리고 양의 수 + 늑대 수가 0보다 클 경우만 최댓

값이 될 수 있다.

 

from collections import deque


def solution(info, edges):
    n = len(info)
    tree = [[] for _ in range(n)]
    answer = 1  # 루트 노드는 양

    for edge in edges:
        tree[edge[0]].append(edge[1])

    # BFS
    queue = deque([[tree[0], 1, 1]])  # 연결 노드, 양의 수 + 늑대 수, 총 양의 수

    while queue:
        data = queue.popleft()

        for idx, next_node in enumerate(data[0]):

            total = data[2]
            if info[next_node] == 0:  # 양
                cal = data[1] + 1
                total += 1

            else:
                cal = data[1] - 1  # 늑대

            if cal > 0:  # 양의 수 > 늑대 수
                queue.append([data[0][:idx] + data[0][idx+1:] + tree[next_node], cal, total])
                answer = max(answer, total)

    return answer


print(solution([0,1,0,1,1,0,1,0,0,1,0], [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]))

 

 

문제에 이진 트리라고 명시되어 있다. 덕분에 사이클을 고려하지 않았다.

다시 말하자면, 1->2->1이 될 경우는 없으므로 확인하지 않았다.

 

그리고 edges의 각 행이 [부모 노드 번호, 자식 노드 번호] 형태로 주어진다.

따라서 양방향을 고려하지 않았다.

예를 들어, 1과 2가 연결되어 있다고만 한다면 어느 것이 부모 노드인지 모르기 때문에

1->2, 2->1을 모두 생각해서 양방향 그래프를 만들어야 한다.

 

 

---

 

시행 착오

 

노드가 1개인 트리가 있을 수 있다. 문제에 따르면 그 노드는 무조건 양이다.

따라서 최댓값이 1이다. 생각없이 최댓값을 0으로 초기화 했다가 틀렸다.