23.04.12 파이썬 코딩 퀴즈#215 양과 늑대 (프로그래머스 스쿨)

이번 문제는 양과 늑대 문제이다.

이진 트리를 이용한 문제인데, 조건은 조금 까다롭다.

먼저 위와 같은 노드를 전달받은 상황을 생각해보자. (입출력 예제 1 이다)

0번 노드는 항상 양이 존재한다.

문제에서 지켜야 하는 규칙은 하나이다.

늑대와 양을 모으는데, 늑대의 수가 양의 수보다 많거나 같다면, 모든 양을 잃게된다.

따라서 8번 노드로는 바로 이동 할 수가 없다.

1번 노드로 이동하면, 모은 양은 2마리가 된다.

이제 이동 가능한 노드는 2번, 4번, 8번이고 모두 늑대가 존재한다

2번 노드 아래에는 양이 더 존재하지 않기 때문에 이동할 필요가 없다.

4번 노드 아래에는 양이 1마리 존재하지만, 현재 모은 양이 2마리 이기 때문에 4번-> 6번 노드를 통과할 수 없다.

8번 노드 아래에는 양이 2마리 존재한다. 따라서 8번으로 이동한다. (양 2, 늑대1)

이제 7번과 9번 노드를 방문하여 양을 모으게 된다. (양 4, 늑대1)

다시 방문 가능한 노드는 2번, 4번, 10번, 11번 노드이지만, 실제 양이 존재하는 길은 4번 노드 하나이다.

4번 노드로 이동 한 후(양4, 늑대2) 3번, 6번 노드로 이동 가능한데 6번 노드 아래에만 양이 존재하기에 6번 이동 후 5번으로 이동한다. (늑대 3, 양 5)

더 이상 모을 양이 없기 때문에 5를 리턴하면 된다.

제한 사항을 살펴보면 info 에는 0은 양, 1은 늑대를 의미한다.

그리고 edges에는 (부모 노드, 자식 노드) 형태로 연결된 정보가 전달된다.

이제 입출력 예 2번을 살펴보자.

전달받은 정보를 이용해 도식화 하면 위와 같은 형태의 이진트리가 구성된다.

이동 순서는 0 -> 2 -> 5 -> 1-> 4-> 8-> 3-> 7-> 6-> 9-> 10 순서로 이동하면 모든 양을 모을 수 있다.

일단 탐색하는 방법에 대해서 좀더 살펴봐야 한다.

10번 노드를 방문하기 위해서는 무조건 2번,6번,9번 노드 순서로 방문해야 한다.

또한 그 조건은 최소한 양이 3마리 있어야지 늑대 2마리를 뚫고 10번에 위치한 양을 가져올 수 있다.

 

이제 코드를 작성해 보자.

먼저 전달받은 edges를 이용해 노드의 연결을 만들어 준다.

그리고 시작은 언제나 0번 노드이기 때문에 [graph[0], 1, 1] 을 q에 넣어주고 while문을 반복하게 된다.

한가지 중요한 점은 3개의 매개변수를 따로 분리하면 안된다는 점이다.

만약 q.popleft()에서 3개의 값으로 분리해 버리면, 그 값은 누적값으로 작용하게 된다. 이를 막기위해 매 반복문을 시행할 때마다 현재 값을 기준으로만 계산하게 해주어야 한다.

해당 코드는 누적값을 사용하는 것이 아닌, 현재 방문한 노드를 기준으로 다음 노드를 진행했을 때 마다의 상황을 가정하여 방문 가능한 위치를 탐색하는 것이 핵심이다. (처음 코드를 누적값으로 잡는 바람에 30분 넘게 고민을 했다...)

 

입출력 1번을 예를 들어 위 코드를 작동시켜 보자.

먼저 q에는 [[1,8], 1, 1] 이 들어가게 된다.

이때 [1,8]을 반복문으로 분리하면 1번, 8번 노드를 확인하게 되는데

1번 노드를 돌게되면 값은 2,2 가 되며 다음에 방문 가능한 노드는 [2,4]이 추가가 된다.

따라서 현재 [1,8] 에서 1번을 제외한 [8]과 [2,4]를 합친 배열 [8,2,4]가 다음에 방문할 배열이 된다.

그리고 q에 추가해줄 요소는 [[8,2,4,], 2, 2] 가 된다.

그 다음이 중요한데, 이제 2,4,8은 모두 늑대가 된다.

만약 여기서 누적값을 사용해 버리면 순서에 따라 [7,9] (8번과 연결된 노드) + [2,4] (남은 노드) , 1, 2 는 추가가 되지만

2번 4번 노드를 방문하면 can_move 값은 0, -1 이 되므로 그 밑에 노드들은 추가되지 않는다. 물론 새롭게 추가된 [[2,4,7,9],1,2] 에 2번 4번 노드가 존재하긴 하지만 누적값을 계속 적용하게 되면 역시 2번 4번은 탈락하게 된다.