넘쳐나는 아이디어 그리고 떨어지는 구현능력

#16940번 BFS 스페셜 저지 https://www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

층별로 돌면서 그 층에 있는 노드들의 다음층 노드에 속하는지 판단하는 코드를 구현하고 싶었다.

 

하지만 맘처럼 잘 되지 않더라...

N = int(input())
matrix = [[] for _ in range(N+1)]

for i in range(N-1):
    prev, to = map(int, input().split())
    matrix[prev].append(to)
    matrix[to].append(prev)
matrix[0].append(1)


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

queue = [0]
idx = 0
for x in target:
    while x not in matrix[queue[idx]]:
        idx += 1
        if idx == len(queue):
            print(0)
            exit()
    queue.append(x)

print(1)

어제부터 자꾸 골드3 문제에서 쓰러진다... 휴,, 

문제는 이렇게 푼다.

1 2 4 3

의 경우를 생각해보자

 

그래프의 경우에

   1

2,    3

4

 

형태로 구성되어 있다.

1번 노드 위에 0번이 있다고 가정한다. (문제를 해결하기 위해 추가한 층이다)

   0      (0번 층)

   1      (1번 층)

2,    3   (2번 층)

4         (3번 층)

 

그리고 0번 층에 해당하는 0번 노드의 다음층에 있는 노드들에 target의 첫 번째 값(1)이 존재하는지 검토한다.

 

있기 때문에 queue에 1을 넣는다.

 

다음 target은 2이다. 현재 queue에 저장되어 있는 값은 0번 층 전부이다.

0의 연결 노드에는 1 뿐이다. 1은 검토가 끝났으니 1의 다음 층에 해당하는 값들 불러온다. (idx += 1)

이게 while 문의 역할이다.

1에 연결되어있는 노드들에 현재  target인 2가 존재하는지 판단한다.

 

존재한다. 2를 queue에 넣어준다.

 

현재 idx = 1이다. queue = [0, 1, 2] 이므로 1을 지칭하고 있다.

 

다음 target은 4이다. 4는 1의 다음 노드에 존재하지 않는다. idx += 1을 해서

2의 다음 노드를 살펴보게한다. 2의 다음 층에는 4가 존재함으로 queue에 4를 넣어준다

문제는 그 다음이다. 현재 탐색함수는 3층으로 진행했다.

하지만 마지막 수인 3은 3층에 존재하지 않는다.

 

뭐 이런식으로 진행되는 코드이다.

 

내가 짠게 아닌지라 설명이 빈약하다.