프로그래머스 [Lv. 3] 양과 늑대 {언어 : Python} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=python3

프로그래머스

정답 코드

from collections import deque

def solution(info, edges):
    answer = 0
    lenI = len(info)
    adjL = [[] for _ in range(lenI)]
    for start, to in edges:
        adjL[start].append(to)
    
    q = deque([(0, 1, 0, set())])
    
    while q:
        current, sheeps, wolves, nodes = q.popleft()
        if answer < sheeps:
            answer = sheeps
        
        # 현재 지점을 갈 것인가
        # 이미 방문한 지점을 갈 것인가
        # 전체 방문 위치 업데이트
        # nodes.update(adjL[current])
        
        # update와 add 차이
        # update는 리스트로 추가 가능 [2, 3, 4]
        # add는 하나씩 추가 가능
        for nextNode in adjL[current]:
            nodes.add(nextNode)
        
        for nextNode in nodes:
            # 늑대
            if info[nextNode]:
                if sheeps > wolves + 1:
                    q.append((nextNode, sheeps, wolves+1, nodes-{nextNode}))
            else:
                q.append((nextNode, sheeps+1, wolves, nodes-{nextNode}))    
        
    return answer

풀이 방법

1. adjL을 만든다.
2. 현재 지점에서 다음 지점을 가거나 가려고 했으나 가지 않은 지점에서 출발하거나 한다.
   1. 쉽게 말해 2번 노드에서 3과 4로 갈 수 있고 4번 노드에서 7과 8로 갈 수 있다면
   2. 4번에서 선택지는 3 7 8이 되고
   3. 3번에서 선택지는 4 7 8이 된다.
3. 현재 방문한 지점에서 양이면 q에 넣고
4. 늑대면 현재 양의 수 - 1보다 많은 경우만 경로 탐색을 한다.
5. 현재 방문 지점에서는 최대 양의 수를 계속 업데이트 해준다.
6. 최대 양의 수를 반환하면 끝!

느낀점

• 트리와 bfs를 섞어서 사용해보는 좋은 경험이었다.
• set도 오래간만에 써봐서 update함수도 알 수 있었다.