[22.01.27] BFS 스페셜 저지 문제

[hyewon11]

Coding_Study/220127_BFS 스페셜 저지/BFS 스페셜 저지_HW.py

Lines 1 to 44 in 0d703d3

	import collections
	import sys
	N = int(input())
	tree_input = [map(int, input().split()) for _ in range(N - 1)]
	answer_order = list(map(int, input().split()))
	visit = [False] * (N + 1)
	# key - value: 서로 연결되어 있는 노드
	tree_info = collections.defaultdict(list)
	for node1, node2 in tree_input:
	tree_info[node1].append(node2)
	tree_info[node2].append(node1)
	# 1부터 시작하는지 확인
	if answer_order[0] != 1:
	print(0)
	sys.exit()
	# input으로 받은 정답 순서대로 딕셔너리 value 정렬
	for i in range(1, N + 1):
	tree_info[i].sort(key=lambda x: answer_order.index(x))
	# BFS
	q = collections.deque()
	q.append(1)
	visit[1] = True
	result = [1]
	while q:
	node = q.popleft()
	adjacency_nodes = tree_info[node]
	child_nodes = []
	# 방문하지 않은 자식 저장
	for adj_node in adjacency_nodes:
	if visit[adj_node] is False:
	child_nodes.append(adj_node)
	result.append(adj_node)
	# 방문하지 않은 자식 q에 넣기
	for child_node in child_nodes[::-1]:
	if visit[child_node] == False:
	q.append(child_node)
	visit[child_node] = True
	print(1) if result == answer_order else print(0)

• node 연결 정보를 tree_info 딕셔너리를 사용해서 인접 리스트로 생성
• 인풋으로 받은 정답 순서를 바탕으로 딕셔너리 value를 미리 정렬 → 정답 순서와 동일하게 트리를 방문하기 위해서 수행
• BFS로 1부터 방문
• BFS: q에 있는 노드를 가져와서 자식 노드들 찾기 → 미리 정렬해둔 순서대로 result에 추가 → 자식 노드 큐에 추가

아니 이젠 뭐가 틀린건지도 안보여요.... 엉엉....😫

[LeeYeonGeol]

일단 반례 드립니다.

7

1 2

1 3

2 4

2 5

3 6

3 7

1 2 3 4 5 6 7

답은 1인데, 0으로 나오는 것같아요. 보시면 느낌오실거라고 생각합니다..!

[hyewon11]

감사합니다!

[LeeYeonGeol]

연휸데,, 쉬엄쉬엄 하십쇼..!