BFS 풀이

유의 사항

바로 아래 코드의 경우 정확성 88.9/100.0점 풀이다.
테스트 케이스 12, 16번이 안 풀린다.

전체 코드

from collections import deque
import copy

SHEEP = 0
WOLF = 1


def bfs(info: list, graph: dict) -> int:
    global SHEEP, WOLF

    max_sheep = 0

    queue = deque()
    visited_set = set()

    # (현재 노드 번호, 양의 개수, 늑대의 개수, 갔던 곳 위치 추적용)
    queue.append((0, 1, 0, [0]))
    
    # 방문 set에 튜플의 상태 정보 저장. (현재 노드 번호, 양의 개수, 늑대의 개수)
    visited_set.add((0, 1, 0))

    while queue:
        node, sheep, wolf, visited = queue.popleft()

        max_sheep = max(max_sheep, sheep)

        for next_node in graph[node]:

            next_sheep = sheep
            # 현재 갔던 경로 중에서 방문한 적이 없고, 양이라면 양의 개수를 +1
            if next_node not in visited and info[next_node] == SHEEP:
                next_sheep += 1

            next_wolf = wolf
            # 현재 갔던 경로 중에서 방문한 적이 없고, 늑대라면 늑대 개수 +1
            if next_node not in visited and info[next_node] == WOLF:
                next_wolf += 1

            # 늑대가 더 많거나 같으면 스킵.
            if next_sheep <= next_wolf:
                continue

            next_state = (next_node, next_sheep, next_wolf)

            # 다음 상태가 방문한 적 없는 상태라면, 
            # 예를 들어 0번 노드를 다시 방문한다고 해도 sheep=1, wolf=0인 상태로 방문하는 것과
            # sheep=2, wolf=1인 상태로 방문한 것은 다르므로 방문 가능합니다. 
            if next_state not in visited_set:
                visited_set.add(next_state)

                # 방문 체킹용 set 깊은 복사
                copy_visited=copy.deepcopy(visited)
                copy_visited.append(next_node)

                queue.append((next_node, next_sheep, next_wolf, copy_visited))

    return max_sheep


def solution(info, edges):
    graph = dict()
    for i in range(len(info)):
        graph[i] = []

    # 양방향 그래프로 만들기
    for i in range(len(edges)):
        u, v = edges[i]
        graph[u].append(v)
        graph[v].append(u)

    return bfs(info, graph)

DFS 풀이

정답 코드

import copy
import sys

sys.setrecursionlimit(10 ** 5)
answer = 0

# can_go와 trace의 조합
visited = set()

# 현재 노드 current에서 갈 수 있는 노드 can_go와 현재 분기까지의 방문 추적용 trace
def recursion(current: int, can_go: set, trace: set, sheep: int, wolf: int, info, tree):
    global answer, visited
    if sheep <= wolf:
        return
    else:
        answer = max(answer, sheep)
        # 현재 노드 current에서 갈 수 있는 영역들 수집
        next_can_go = copy.deepcopy(can_go)
        next_trace = copy.deepcopy(trace)

        for adj in tree[current]:
            if adj not in next_trace:
                next_can_go.add(adj)

        # 현재 노드는 재방문 하지 않도록 처리
        next_trace.add(current)

        # 방문할 수 있는 곳들에 대해
        for next_node in next_can_go:
            # 다음 분기에 갈 곳을 정했으면, 갈 수 있는 곳에서 일단 뺀다.
            next_can_go.remove(next_node)

            # 현재 갈 수 있는 곳과 가본 곳의 조합이 방문한 적 없는 상태라면
            if (tuple(next_can_go), tuple(next_trace)) not in visited:
                visited.add((tuple(next_can_go), tuple(next_trace)))

                if info[next_node] == 0:
                    recursion(next_node, next_can_go, next_trace, sheep + 1, wolf, info, tree)
                else:
                    recursion(next_node, next_can_go, next_trace, sheep, wolf + 1, info, tree)

            # 분기를 마쳤으면, 다시 넣는다.
            next_can_go.add(next_node)
            
def solution(info, edges):
    tree = dict()
    for parent, child in edges:
        if parent not in tree:
            tree[parent] = []
        if child not in tree:
            tree[child] = []

        tree[parent].append(child)
        tree[child].append(parent)

    recursion(0, set(), set(), 1, 0, info, tree)

    return answer

해설

먼저 현재 노드에서 갈 수 있는 노드 집합 next_can_go, 갔었던 노드 집합 next_trace를 구한다.

그리고 다음 분기를 보기 위해 next_node를 기준으로 재귀호출해야 한다. next_node에 대해 재귀호출해야 하므로 next_can_go에서 remove해야 한다.

그렇지 않을 경우 다음 분기에서 current가 can_go에 존재하게 되는, 무한 루프가 발생할 수 있다.

그리고 next_can_go와 next_trace 집합으로 만든 조합이 도달한 적 없는 상태라면, 다음 분기를 실시 할 수 있다.