(Python/파이썬) - 백준(BOJ) 16940번 : BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

---

• 문제 : 

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

 

1. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
2. 큐가 비어 있지 않은 동안 다음을 반복한다.
   1. 큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
   2. x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.

 

2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.

트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구해보자.

 

 

 

---

• 풀이 :

BFS 외에 추가적인 아이디어가 필요한 구현 문제였습니다.

처음에 골드 3 치곤 너무 쉽다고 생각하고 금방 풀었는데 당연하게도 바로 틀렸습니다...

 

처음 접근입니다.

 

1. BFS로 탐색을 진행하는데 visited의 값 (트리의 level 또는 height를 의미합니다.) 을 기준으로 집합을 만들고 

주어진 케이스를 각 레벨의 노드 개수만큼 잘라 같은지 비교합니다. 다르다면 0을 출력하고 종료합니다.

 

코드입니다.

# 백준 16940 BFS 스페셜 저지
from collections import deque
import sys
input = sys.stdin.readline

start = 1
N = int(input())
graph = [[] for _ in range(N+1)]
visited = [-1 for _ in range(N+1)]
visit_case = [set() for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
test_case = list(map(int,input().split()))


#BFS
queue = deque()
queue.append(start)
visited[start] = 0
while queue:
    x = queue.popleft()
    for i in graph[x]:
        if visited[i] == -1:
            visited[i] = visited[x] + 1
            visit_case[visited[x]+1].add(i)
            queue.append(i)

index = 1
for case in visit_case[1:]:
    for _ in range(len(case)):
        if test_case[index] not in case:
            print(0)
            exit()
        index += 1
print(1)

 

이 풀이의 반례는 이것입니다.

 

입력 : 
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 6 7 4 5

출력  0

내 결괏값 : 1

 

틀린 이유는 다음과 같습니다.

 

- 1번 노드의 자식인 2번과 3번 노드를 탐색할 때 입력값인 2번 다음 3번의 순서로 탐색한다면 level이 2인 노드의 탐색 순서는 4 5 6 7이 되어야 합니다.

 

저의 풀이에서는 부모의 접근 순서를 고려하지 않고 같은 level의 노드들이 같은지만 고려해서 틀린 것입니다.

따라서, 다른 접근 방법을 찾아야 했습니다. 

 

문제를 해결한 알고리즘의 흐름은 다음과 같습니다.  

 

1. BFS는 처음 방법과 똑같이 진행, 그러나 각 level의 노드들을 기록하는 것이 아닌 부모와 자식 관계를 children 배열을이용해서 기록.

 

2. test_case의 각 숫자별로 비교를 진행하는데 이 때, next_index라는 변수 사용.  이 변수는 현재 탐색중인 노드(i)의 자식 노드들이 어떤 인덱스값부터 시작해야 하는지 저장하기 위함 

 

예를 들어, 위의 예제에서 

 

1을 탐색할 땐 1의 자식이 index 1부터 시작하므로 1입니다.

2를 탐색할 땐 2의 자식이 index 3부터 시작하므로 3입니다.

3을 탐색할 땐 3의 자식이 index 5부터 시작하므로 5입니다.

 

3. next_index부터 현재 탐색중인 노드의 자식 개수만큼 test_case를 슬라이스한 값과 현재 탐색중인 노드의 자식들을 비교하여 다르다면 0을 출력.

 

추가 아이디어) children을 set으로 사용한 이유는 자식들의 순서는 고려하지 않아도 되기 때문입니다. 또한, next_index가 N과 같아진다면 leaf node들을 탐색하는 것이므로 자식 노드를 확인할 필요가 없어 반복문을 종료해 주었습니다.

 

 

 

 

 

---

• 소스코드 : 

# 백준 GOLD III 16940 BFS 스페셜 저지

from collections import deque
import sys
input = sys.stdin.readline

start = 1 # 시작점
N = int(input())
graph = [[] for _ in range(N+1)]
visited = [-1 for _ in range(N+1)] # BFS시 탐색 여부 확인을 위함
children = [set() for _ in range(N+1)] # 트리의 부모자식 관계를 알기 위함
for _ in range(N-1): # 그래프 생성
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
test_case = list(map(int,input().split())) # 비교할 탐색 루트

# BFS
queue = deque()
queue.append(start)
visited[start] = 0
while queue:
    x = queue.popleft()
    for i in graph[x]:
        if visited[i] == -1:
            visited[i] = visited[x] + 1 # 방문처리
            children[x].add(i) # x의 자식은 i이다.
            queue.append(i)


next_index = 1
for i in test_case:
    if next_index == N:
        break
    c_length = len(children[i]) #자식의 길이
    c1 = set(test_case[next_index : next_index+c_length])
    c2 = children[i]
    if c1 != c2:
        print(0)
        exit()
    next_index += c_length
print(1)