문제 링크
풀이 과정
•
노드를 방문해야, 양을 획득할 지 늑대를 획득할 지 알 수 있습니다.
◦
즉, 노드를 방문하기 이전에 양을 최대로 모을 수 있는 방법을 알아낼 수 없습니다.
◦
따라서, 완전 탐색 방식으로 접근해야 합니다.
•
완전 탐색을 위한 고려 사항은 다음과 같습니다.
◦
백트래킹 기준 → 현재 양의 수와 늑대의 수가 같은가?
◦
다음에 방문 가능한 노드를 찾는 방법
▪
출발지 노드는 방문한 상태이며, 목적지 노드는 아직 방문하지 않았는지 확인
◦
최대로 얻을 수 있는 양의 수를 계산하는 방법
▪
각 탐색 경로마다 얻을 수 있는 양의 수를 계산합니다.
▪
서바이벌 방식으로 최댓값을 갱신합니다.
전체 코드
def solution(info, edges):
'''
1. 각 노드를 탐방하면서 현재까지 모은 양과 늑대의 수를 체크
- 양의 수와 늑대 수가 같다면, 해당 경로는 탐방 종료
2. 방문한 노드를 다시 방문할 수 있도록(양을 얻기 위해서) 처리
- 노드 탐험 가능 여부?
- 연결된 노드 간 자유롭게 이동
DFS
task: 현재 노드에서 최대한 모을 수 있는 양의 수를 구하는 것
다른 노드에 위임할 것
1) 종료 조건 확인: 양의 수와 늑대 수가 같은지?
2) 현재까지 얻은 양의 수를 저장
3) 탐험 가능한 노드 탐색 후, DFS 재귀 호출
4) 3)번에서 찾은 노드를 다시 방문할 수 있게 0 처리
'''
def dfs(cur_sheep, cur_wolf):
nonlocal sheep
if cur_sheep == cur_wolf: return
if cur_sheep > sheep: sheep = cur_sheep
for start, end in edges:
if visited[start] == 1 and visited[end] == 0:
visited[end] = 1
if info[end] == 0: dfs(cur_sheep+1, cur_wolf)
else: dfs(cur_sheep, cur_wolf+1)
# 목적지 노드는, 다른 탐색 경로를 통해 다시 방문할 수 있습니다.
# 따라서, 깊이 우선 탐색이 끝났을 때 visited 값을 0으로 합니다.
visited[end] = 0
sheep, wolf = 1, 0
visited = [0 for _ in range(len(info))]
visited[0] = 1
dfs(sheep, wolf)
return sheep
Python
복사