[Python] 프로그래머스(2022카카오 신입 공채) 양과 늑대(DFS?)

문제

문제 설명

문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

---

입출력 예

info	edges	result
[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
[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]]	5

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

주어진 입력은 다음 그림과 같습니다.

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.

---

제한시간 안내

• 정확성 테스트 : 10초

풀이

풀고 나서도 으잉? 했다.

마치 dfs인 척 하는 문제인 것처럼 느껴졌다.

물론 나는 전문 적인 사람이 아니기 때문에 확정을 못하지만... 평소에 풀던 dfs와는 완전히 다른 느낌이었다.

일단 기본적인 아이디어는 "node를 가보는 순서의 경우의 수를 모두 탐색한다."이다.

dfs는 보통 한번 탐색한 곳은 다시 가볼 일이 없지만, 이번 문제는 한번 가 보았다가 늑대가 많아져서 포기한 곳도 나중에 다시 탐색해야 한다는 점이 있다.

따라서 귀찮게 "못 가본 곳은 기억해 놓았다가 다른 곳 갔다가~ 다시 돌아 왔을 때 또 못 가면 그땐 진짜 포기해야지~"같은 방식 보단 "모든 순서의 경우의 수" 이 상태 공간을 기준으로  dfs를 탐색하는 것이 더 쉽다.

내가 푼 풀이는 먼저 매개 변수 하나를 지정하는데 이 매개변수는 "아직 가보지 못한 노드"를 의미한다. 이것을 notVisited라고 하자.(실제로는 비트 마스크를 사용하였다.)

notVisited에 노드를 추가할 때는 "현재 노드에 연결되어 있는 노드"만을 추가 한다.

즉, 한 노드에 방문하는 즉시 notVisited변수에 현재 방문한 노드를 지운 후, "현재 노드에 연결되어 있는 노드"를 추가한다.

그 다음 이 notVisited 변수를 기준으로 for문을 돌려 재귀 호출을 한다. 아직 방문하지 않은 노드들을 차례차례 탐색하는 것이다.

이 때에 notVisited를 dfs함수에 다 넣어준다.

그리고 위의 말 대로 탐색 하였을 때(dfs 함수 진입 시), 양보다 늑대가 많거나 같다면 그냥 return해 버린다.

"다른 노드를 먼저 탐색하고 나중에 양이 더 많아졌을 때 다시 탐색해야 하는 거 아냐?"라고 할 수 있지만 이 경우는 그냥 "노드를 방문하는 순서가 틀려 먹었네. 다른 노드를 먼저 가는 dfs 함수도 있으니까 여기서 난 끝!"인 것이다...

진짜 운 좋은 사람이 있다고 치자. 그럼 그 사람은 운 좋게 양만 있는 곳을 쏙쏙 잘 골라서 돌아다닐 것이다.

마찬가지로 이 수 많은 재귀 함수들 중  한 함수는 운 좋게 최댓값을 출력할 것이다.

그러니까 그냥 노드를 순서대로 배치하는 경우의 수를 모두 탐색하는 것과 다를 바가 없다...

다른 것이 있다면 그저 한 노드를 방문하기 전에 방문해야 하는 필수 노드들(부모 노드)이 있다. 정도?

보통 dfs를 풀 때에는 주어진 트리 그 자체의 상태 공간을 탐색하지만 이번 문제는 notVisited에 추가, 삭제를 하면서 notVisited의 상태 공간을 탐색하는 것이다.

참 특이한 문제였지만, 찝찝하기도 한 문제였던 것 같다.

import sys

sys.setrecursionlimit(100)

def dfs(count, sheep, wolf, info, tree, start, candidate):

    candidate = candidate & ~(1 << start)

    if info[start] == 1:

        wolf += 1

    else:

        sheep += 1

    if wolf >= sheep:

        return

    count[0] = max(count[0],sheep)

    for i in tree[start]:

        candidate |= 1 << i

    bit = 0b1

    index = 0

    while candidate >= bit << index:

        if candidate & (bit << index):

            dfs(count, sheep, wolf, info, tree, index, candidate)

        index += 1

    return

def solution(info, edges):

    answer = 0

    tree = [[] for _ in info]

    for s, e in edges:

        tree[s].append(e)

    count = [0]

    dfs(count, 0, 0, info, tree, 0, 0b0)

    return count[0]

결과