[ 프로그래머스 ] 양과 늑대 (Python)

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

 

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DFS, BFS 
풀이 시간 : 43분 

문제 풀이 

이진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여있다. 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다. 만약 늑대를 만나면 늑대가 양을 따라다니게 되고, 늑대의 수가 양의 수보다 같거나 큰 경우 모든 양을 잡아먹는다. 최대한 많은 양을 모으자.

 

문제는 이진 트리 형식으로 되있고, DFS와 BFS 모두 사용가능하다. 다만, 이 문제는 방문 처리를 해 가면 안된다. 그 이유를 그림을 통해 알아보자.

0번 노드에서 방문할 수 있는 노드는 1번과 2번이다. 하지만, 1번으로 가게 되는 경우, 양과 늑대의 수가 같아지기 때문에 우리는 2번 노드를 먼저 방문해야 한다.

2번 노드에서 방문할 수 있는 노드는 5번, 6번이다. 만약 5번을 방문한 경우, 양과 늑대의 수는 3 : 0이 된다.

최대 양의 수 : 4

만약 5번 노드까지 방문한 다음, 6번 노드로 갔다고 가정해보자. 이런 경우, 10번 노드까지 방문했을 때 양과 늑대의 수는 4 : 2가 된다. 이렇게 됬을 때, 다시 올라와서 1번, 3번 노드 순서로 방문하거나 1번, 4번 노드 순서로 방문하는 경우, 양과 늑대의 수가 4 : 4가 되어 최대 4마리를 끌고다닐 수 있게 된다.

7번 노드까지 들렀다가 8번 노드도 갈 수 있게된다.

하지만, 만약 5번 노드까지 방문한 뒤, 6번 노드가 아닌 1번 노드로 향했다면, 양과 늑대의 수가 3 : 2가 되어 7번 노드까지 이동할 수 있게 된다. 이렇게 되면 양과 늑대의 수가 4 : 2가 되기 때문에, 8번 노드까지 방문할 수 있다. 따라서 최대 5마리의 양을 끌고다닐 수 있다.

 

위 그림에서 노드 방문 순서를 보면, 일반적인 BFS를 따르지 않는 것을 확인할 수 있다. 따라서 BFS에 사용되는 큐의 원소 정보에 현재 노드에서 방문가능한 다른 노드 정보를 추가로 넣어주었다.

이후, graph[현재 노드]에 대해서만 탐색하는 것이 아닌, 현재 방문가능한 노드에 대해서 탐색을 진행해주었다.

현재 방문가능한 노드 정보는 `set()` 객체를 사용하여 중복되는 노드들에 대해 제거해주었다.

 

코드

'''
루트 노드부터 시작하여, 최대한 많은 수의 양을 모으는 경우를 구하자

-> dfs, bfs 두 방법 모두 가능할듯
일단 양과 늑대의 수를 구해야 한다.
bfs로 해보기 
1. 현재 큐에는 있지만 가보지 않은 경우에 대한 정보를 담은 큐도 필요함
2. 현재 위치에서 가볼만한 다음 위치를 저장해놓기 위한 배열 필요함
'''

from collections import deque

def solution(info, edges):
    answer = 0
    n = len(info)
    graph = [[] * n for _ in range(n)]
    for s, e in edges:
        graph[s].append(e)
    
    queue = deque([(0, 0, 0, set())])      # 노드, 양, 늑대, 방문 배열
    visited = [0] * n
    
    while queue:
        u, sheeps, wolves, path = queue.popleft()
        # 먼저, 현재 위치의 양, 늑대 정보 업데이트
        if not info[u]:
            sheeps += 1
        else:
            wolves += 1
        # continue 조건    
        if sheeps <= wolves:
            continue
        answer = max(answer, sheeps)
        
        tmp_path = set(graph[u])
        tmp_path.update(path)
        # print(u, sheeps, wolves)
        for v in tmp_path:
            queue.append((v, sheeps, wolves, tmp_path.difference(set([v]))))

    return answer

배운 점 

위 문제를 만약 DFS로 풀게 된다면, 한 정점을 새로 방문할 때마다 주어진 edge 정보를 모두 탐색해보며 가능한 경우에 대해 DFS를 진행하는 방법으로 풀 수 있을 것 같다.

어떻게보면 완전탐색적으로 풀이가 가능하다. 요즘 듣고있는 알고리즘 강의에서 문제를 우선 완전탐색적으로 생각해나가라고 했는데, 무작정 알고리즘을 적용하기보다는 문제에 접근하는 가장 기초적인 시각을 탑재할 수 있도록 재정비를 진행해야 할 것 같다.