공부 194일차: 백준 16940번 BFS 스페셜 저지 자바 java

16940 BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

 

 

 

 

---

백준 16940번 문제 BFS 스페셜 저지

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	7688	2064	1242	24.473%

문제

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

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/345

공부 192일차: 백준 16964번 DFS 스페셜 저지 자바 java

매우 유사한 문제

 

https://gimbalja.tistory.com/328

공부 181일차: 백준 1260번 DFS와 BFS 자바 java

이 문제로 DFS와 BFS 코드를 어떻게 구현하는지 한눈에 비교해보는 것도 문제를 이해하는 데 도움이 될 것 같다

 

트리 구조인 이 문제에서, 1번부터 BFS 탐색을 시작할 때

2로 갈지, 3으로 갈지를 고를 수 있다

어느 것을 선택해도 깊이 우선 탐색이라는 사실은 변하지 않으므로 1 2 3 4 / 1 3 2 4 모두 가능하다

 

그래서 가능한 자식 노드들의 경우를 저장해야 한다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int idx = 1;    // 두번째부터 비교.확인
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visited;
    static int[] store;
    static int result = 1;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        store = new int[n];
        visited = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        
        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            // 양방향
            list.get(x).add(y);
            list.get(y).add(x);
        }
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            store[i] = Integer.parseInt(st.nextToken())-1;
        }
        
        if(store[0] != 0) {    // 시작점이 달라지면 프로그램 종료
            System.out.println(0);
            return;
        }
        
        bfs(0);
        System.out.println(result);
    }
 
    static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);    // 탐색 시작
        visited[x] = true;    // 방문 처리
        
        while(!q.isEmpty()) {
            HashSet<Integer> set = new HashSet<>();
            
            int val = q.poll();
            
            // 가능한 경로 확인
            for(int next : list.get(val)) {
                if(!visited[next]) {
                    set.add(next);
                    visited[next] = true;
                }
            }
            
            int size = set.size();
            if(size == 0) {
                return;
            }
 
            for(int i = idx; i < idx+size; i++) { // 다음 자리부터 가능한 자리까지
                if(set.contains(store[i])) {    // set에 들어가있다 == 자식 노드다
                    q.add(store[i]);            // 큐에 넣기
                }else {
                    result = 0;
                    return;
                }
            }
            idx += size;
        }
    }
}
 

 

 

 

---

dfs를 먼저 풀어서 수월했다

확실히 dfs보다 bfs가 더 어렵게 느껴지긴 하지만~