[프로그래머스] 양과늑대 복기

문제

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

#양을 모아야함
#해당 노드에 있는 양과 늑대가 따라옴
#양의 수보다 늑대의 수가 같거다 더 많으면 양을 잡아 먹음
#최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아와야함
from collections import deque

def solution(info, edges):
    answer = 0
    graph = [[] for _ in range(len(info))]
    queue = deque()
    
    for a,b in edges:
        graph[a].append(b)
    queue.append([[0],1,0])
    max_cnt = float("-inf")
    

    #0이 양, 1이 늑대
    while queue: #queue = [[방문경로], 양, 늑대]
        top = queue.popleft()  
        
        max_cnt = max(max_cnt, top[1])
          
        for visited in top[0]: # 방문노드의 인접노드
            for link in graph[visited]:
                if link in top[0]:
                    continue
                visits = top[0][:]
                visits.append(link)

                if info[link] == 1: # 늑대인 경우
                    if top[1] <= top[2]+1:
                        continue
                    else:
                        queue.append([visits,top[1],top[2]+1])
                else:
                    queue.append([visits,top[1]+1,top[2]])
                        
    
    if max_cnt == float("-inf"):
        return 0
    
    return max_cnt

#공부할 것 중간에 continue 여부

생각해봐야할 것

• 문제 이해가 부족했다. 루트 노드까지 도달해야 된다고 생각했는데 test case 1번 문제에서 루트노드까지 확인 여부를 뺐더니 맞았다.

• 만약 늑대의 수가 양의 수보다 많아지면 queue에 append 해서는 안된다. 왜일까...? 나는 양의 수가 0으로 초기화 되어도 이후 노드에 모두 양이 존재하면 더 많은 양의 수를 가질 수 있다고 생각했다. 하지만 0이 되는 양의 수를 피해가야지만, 현재 존재하는 1마리 양의 수를 지킬 수 있다.

• 방문 순서를 queue[0]에 저장했다. 그리고 방문했던 노드들의 인접 노드를 방문할 수 있도록 했다.