문제 설명
•
주어진 2진 트리 구조에서 늑대에게 잡아먹히지 않도록 양을 최대한 많이 모을 수 있는 경로를 찾는 문제
예제 입력/출력
info | edges | result |
[0,0,1,1,1,0,1,0,1,0,1,1] | [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] | 5 |
[0,1,0,1,1,0,1,0,0,1,0] | [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] | 5 |
제약 조건
•
◦
info의 원소는 0(양) 또는 1(늑대)
문제 풀이
접근1 브루트 포스 -
접근2 그리디
접근3 BFS - 상한
풀이 코드
•
접근3 BFS - 상한
from collections import deque
def solution(info, edges):
N = len(info)
adj_list = [[] for _ in range(N)]
for a, b in edges:
adj_list[a].append(b)
adj_list[b].append(a)
visited = set()
ans = 0
q = deque()
q.append(({0}, 1, 0)) # (상태 집합, 양의 개수, 늑대의 개수)
while q:
cur_set, cur_sheep, cur_wolf = q.popleft()
ans = max(ans, cur_sheep)
nxt_nodes = set()
for node in cur_set:
for adj_node in adj_list[node]:
if adj_node not in cur_set:
nxt_nodes.add(adj_node)
for node in nxt_nodes:
nxt_set = cur_set | {node}
if info[node] == 0:
if tuple(sorted(nxt_set)) not in visited:
q.append((nxt_set, cur_sheep + 1, cur_wolf))
visited.add(tuple(sorted(nxt_set)))
elif info[node] == 1 and cur_sheep > cur_wolf + 1:
if tuple(sorted(nxt_set)) not in visited:
q.append((nxt_set, cur_sheep, cur_wolf + 1))
visited.add(tuple(sorted(nxt_set)))
return ans
Python
복사