양과 늑대 (92243번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

프로그래머스 - 양과 늑대 (92243번)

 

난이도 : Lv.3

알고리즘 : DFS (Depth First Search)

풀이 소요 시간 : 120분

기출 : 2022 KAKAO BLIND RECRUITMENT

 

def solution(info: list, edges: list) -> int:
    def dfs(pn: int, sheep: int, wolf: int, an_list: set):
        nonlocal answer

        if not info[pn]:
            sheep += 1
            answer = max(answer, sheep)
        else:
            wolf += 1

        if sheep <= wolf:
            return

        for cn in an_list:
            nan_list = an_list.copy()
            nan_list.remove(cn)
            for ccn in graph[cn]:
                nan_list.add(ccn)
            dfs(cn, sheep, wolf, nan_list)
        return

    
    answer = 0
    graph = [set() for _ in range(len(info))]
    for p, c in edges:
        graph[p].add(c)
    dfs(0, 0, 0, graph[0])
    return answer

 

이런저런 시도 해보다가 시간이 상당히 오래 걸렸다.

우선순위 큐도 적용해보고, DP도 시도해봤지만

부모 노드의 늑대를 카운트하면, 자식 노드들의 늑대 수도 모두 하나씩 줄어드는 문제 때문에

우선순위 큐 적용이 어려웠다.

 

그래서 결국 DFS로 해결했다.

 

 

 

0 (root node) 부터 시작해서 자식노드들을 하나씩 탐색하는데,

일반적인 DFS와의 차이점은, 다음에 방문할 후보 노드들이 계속 누적되는 부분이다.

(이미 방문한 노드는 제외)

 

예를 들어, 현재까지 [0, 1, 8] 세 노드를 방문했다면,

다음 방문 후보로는

▷ 0의 자식 노드 [1, 8]

▷ 1의 자식 노드 [2, 4]

▷ 8의 자식 노드 [7, 9]

를 모두 합한 [1, 8, 2, 4, 7, 9] 가 된다.

 

이 중 [1, 8] 은 이미 앞에서 방문했기 때문에 제외하면,

최종적으로 [2, 4, 7, 9]가 다음 DFS 방문 후보 노드들이 된다.

 

이런 식으로 DFS를 진행하면,

그래프에서 수집 가능한 최대 양의 수를 정확하게 구할 수 있다.

 

---

 

괜히 우선순위 큐, DP on Tree 등으로 고민하면서 어렵게 풀다가 시간만 많이 걸렸다.

앞으로는 좀 더 간단하게 푸는 방법부터 먼저 적용해보는 연습을 해야겠다.