이 문제는 dfs를 통해 양이 가장 많은 경로가 무엇인지 알아내야 한다.
- 방문한 노드를 기록하기 위한 visited 배열 선언
- dfs 함수 선언
2-1. 양의 수가 늑대보다 많을 경우, answer에 양의 수 추가하고, 적은 경우 return
2-2. for문을 통해 갈 수 있는 노드를 확인하여 갈 수 있는 곳으로 이동하고, 방문 노드를 visited에 기록
2-3. 위 과정을 dfs 방식으로 반복한다.
- answer 중 가장 높은 값을 return 해준다.
def solution(info, edges): visited = [0] * (len(info)) # 문제 풀이 1번 visited[0] = 1 answer = [] # 문제 풀이 2번 def dfs(sheep, wolf): # 문제 풀이 2-1번 if sheep > wolf: answer.append(sheep) else: return # 문제 풀이 2-2번 for i in range(len(edges)): parent = edges[i][0] child = edges[i][1] isWolf = info[child] if visited[parent] and not visited[child]: visited[child] = 1 dfs(sheep+(isWolf==0), wolf+(isWolf==1)) # 문제 풀이 2-3번 visited[child] = 0 dfs(1,0) return max(answer) # 문제 풀이 3번