[파이썬] 16940. BFS 스페셜 저지

문제

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

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

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

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

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

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

예제 입력 1 

4
1 2
1 3
2 4
1 2 3 4

예제 출력 1 

1

올바른 순서는 1, 2, 3, 4와  1, 3, 2, 4가 있다.

예제 입력 2 

4
1 2
1 3
2 4
1 2 4 3

예제 출력 2 

0

 

 

🔥 나의 풀이

# 트리가 주어진 올바른 BFS 방문 순서라면 1을 출력하는 문제
# BFS를 이용해 노드별 자식 노드를 구한다
# set을 이용해 방문한 노드의 개수만큼 방문 순서를 비교했다
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())        # 정점의 개수(2 <= N <= 100,000)
tree = [[] for n in range(N+1)]
for n in range(N-1) :
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

visit_order = list(map(int, input().split()))        # BFS 방문 순서
connection_tree = [[] for n in range(N+1)]

def bfs() :
    q = deque([1])
    visited = [0] * (N+1)
    while q :
        x = q.popleft()
        visited[x] = 1
        for y in tree[x] :
            if not visited[y] :
                q.append(y)
                connection_tree[x].append(y)

if visit_order[0] == 1 :
    bfs()
    que = deque([1])
    idx = 1
    while que :
        x = que.popleft()
        child_x = set(connection_tree[x])   # x의 자식 노드들
        len_childX = len(child_x)
        input_order = visit_order[idx : idx + len_childX]
        set_input_order = set(input_order)
        idx += len_childX
        que.extend(input_order)
        if child_x != set_input_order :
            print(0)
            break
    else :
        print(1)
else :          # 1부터 시작하지 않는 입력 순서
    print(0)

다른 사람 풀이 참고(BFS 탐색으로 자식 노드를 구하는 것, 입력의 순서가 1로 시작하지 않으면 0 출력)

마지막 입력으로 주어진 순서가 1로 시작하지 않으면 0을 바로 출력한다.

BFS 탐색으로 1번부터 시작해서 순회하며 자식 노드들을 기록한다.

BFS 탐색으로 얻은 자식 노드들을 입력으로 주어진 순서와 비교한다.

⚠️ que에 set_input_order를 넣으면 틀린다.

set은 순서가 유지가 안 되니까 input_order를 넣는 것과 set_input_order를 넣는 것은 다르다.

 

 

# 틀렸습니다
# 트리가 주어진 올바른 BFS 방문 순서라면 1을 출력하는 문제
# 방문한 노드의 개수만큼 방문 순서를 비교했다
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())        # 정점의 개수(2 <= N <= 100,000)
tree = [[] for n in range(N+1)]
for n in range(N-1) :
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

visit_order = list(map(int, input().split()))        # BFS 방문 순서
visit = [0] * (N+1)
que = deque([1])
set_visit = set([1])
idx = 1

while que :
    x = que.popleft()
    visit[x] = 1
    for y in tree[x] :
        if not visit[y] :
            que.append(y)
            idx += 1
            set_visit.add(y)
    if set_visit != set(visit_order[ : idx]) :
        print(0)
        break
else :
    print(1)

이전의 통과한 코드처럼 BFS로 탐색한 트리의 간선 정보를 활용해야한다.

 

 

🌿 다른 사람 풀이

# https://dalseoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-16940-BFS-%EC%8A%A4%ED%8E%98%EC%85%9C-%EC%A0%80%EC%A7%80
import collections
import sys

input = sys.stdin.readline

def bfs() :
    q = collections.deque()
    q.append(1)     # 시작 정점 1
    visited[1] = 1

    while q :
        x = q.popleft()
        for y in abj[x] :
            if visited[y] != 0 : continue
            visited[y] = visited[x] + 1
            children[x].append(y)
            q.append(y)

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

children = collections.defaultdict(list)
visited = [0] * (N + 1)

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

if res[0] != 1 :    # 시작 정점이 1이 아니면
    print(0)
else :
    bfs()

    q = collections.deque()
    q.append(1)
    idx = 1

    while q :
        tmp = q.popleft()

        a = set(children[tmp])

        len_a = len(a)
        b = res[idx : idx + len_a]
        q.extend(b)
        b = set(b)
        idx += len_a

        if a != b :
            print(0)
            break
    else :
        print(1)

주어진 마지막 입력이 1번부터 시작하지 않으면 바로 답을 출력한다.

 

 

문제 출처 👉 백준