[파이썬/python] 백준 - 16940 BFS 스페셜 저지

문제

https://www.acmicpc.net/problem/16940

---

문제 설명

1. 정점의 개수가 N개, 1부터 N까지 번호가 매겨져있는 양방향 그래프가 존재한다.
2. 노드의 탐색 순서가 입력으로 주어진다.
3. BFS 알고리즘을 실행했을 때 가능한 탐색 순서가 맞는지 확인하는 스폐셜 저지 문제를 만들어야 한다.
4. 주어진 입력이 올바른 방문 순서인지 검사한다.

 

---

풀이

처음엔 BFS 탐색을 통해 깊이 별 노드들을 담아 순서가 맞는지 탐색하려고 했다.

하지만 문제가 1개 있었다. 같은 깊이지만 서로 다른 노드에서 뻗어진 자식이라면 부모의 순서에 따라 자식의 방문 순서도 생긴다는 것이다.

따라서 슬라이딩 윈도우를 이용하여, 방문 순서를 탐색했다.

s = 부모 노드

e = 자식 노드

s가 e를 자식으로 가지면 e를 1 증가시켜 다음 자식을 탐색한다.

현재 자식을 가지지않는다면 s를 증가시켜 다음 부모가 가질 수 있는지 탐색한다.

 

가능 조건은 다음과 같다.

1. 자식이 while문을 먼저 탈출한다.

 

불가능 조건은 다음과 같다.

1. 부모가 while문을 먼저 탈출한다.

2. s가 e와 같아진다.   

   

1. s = 0, e = 1로 초기화한다.
2. 슬라이딩 윈도우를 통해 현재 방문 순서가 탐색 가능한 순서인지 검사한다.
   1. 자식을 포함한다면 e를 1 증가한다.
   2. 포함하지 않는다면 s를 1 증가한다.
3. 위 조건에 따라 결과를 출력한다. 

---

코드

import sys
input = sys.stdin.readline
n = int(input())
graph = [set() for _ in range(n+1)]

for i in range(n-1):
    v1,v2 = map(int,input().split())
    graph[v1].add(v2)
    graph[v2].add(v1)
seq = list(map(int,input().split()))
if seq[0] != 1:
    print(0)
    exit()
s = 0
e = 1

while s < e and e < n:
    if seq[e] in graph[seq[s]]:
        e += 1
    else:
        s += 1
if s == n-1 or s == e:
    print(0)
else:
    print(1)

 

---

시간복잡도

• 슬라이딩 윈도우의 시간 복잡도는 $O(N)$이다.
• 최악의 경우 $N = 10^5$이므로 시간복잡도는 약 $O(10^5)$이다.