글 읽기 - [python3] 어디가 틀렸을까요..?

112224 2년 전 0

1. 시작 정점을 1로 하여 BFS를 진행하며 각각의 노드에 level 정보를 갱신해줍니다.

2. 방문 순서를 저장합니다.

3. 입력으로 받은 방문 순서와 만들어진 방문 순서를 순회하며 각각의 level 값을 비교합니다.

주어진 그래프는 트리이므로 틀린 부분이 없다고 생각하였는데 WA를 받았습니다.

반례나 틀린 부분 지적해주시면 감사하겠습니다 ㅠ

import sys
input = sys.stdin.readline

from collections import deque

n = int(input())
adj = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

tmp_ans = list(map(int, input().split()))

level = [0] * (n+1)
visit = [False]*(n+1)
ans = []
#1
q = deque()
visit[1] = True
q.append(1)

while q:
    now = q.popleft()
    ans.append(now)

    for ele in adj[now]:
        if not visit[ele]:
            visit[ele] = True
            #2
            level[ele] = level[now] + 1
            q.append(ele)

ret = 1
#3
for i, j in zip(ans, tmp_ans):
    if level[i] != level[j]:
        ret = 0
        break
print(ret)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python3] 어디가 틀렸을까요..?

112224 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말