[백준] code.plus(그래프 알고리즘,JAVA)16940번, BFS 스페셜 저지

문제 링크

16940번: BFS 스페셜 저지

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 그래프에 대하여 BFS 탐색하는 순서가 올바르면 1, 올바르지 않으면 0을 출력합니다.

2. BFS결과는 여러가지 나올 수 있습니다.

3. 항상 시작 정점은 정점 1입니다.

 

아래와 같은 그래프가 주어졌을 때

정점 1부터 BFS탐색을 진행하면 아래의 범위에 순서로 탐색을 진행하며

같은 계층에서 어느 지역을 먼저 탐색하는 것은 어떤 정점이 먼저 탐색되었는가에 따라 다릅니다.

만약 루트 1에서 정점 2, 3으로 탐색된다면 정점 4가 먼저 탐색되며 정점 3이 먼저 탐색되었다면 5,6이 먼저 탐색합니다.

 

 

 

위 특징을 이용하여 지역에 포함된 정점을 HashSet에 저장한 뒤에 입력받은 순서에 맞게 저장되어 있는지 확인하는 것을 반복하여 입력된 모든 순서를 처리하면 1을 처리하지 못하면 0을 결과로 출력합니다.

 

예제입력1

항상 시작 정점은 1이기 때문에 1부터 탐색합니다.

입력된 순서 : 1, 2, 3, 4

1을 탐색으로 1 제거

 

HashSet : 2 ,3

입력된 순서 : 2, 3, 4

2, 3 탐색으로 제거

HashSet : 4

입력된 순서 : 4

4 탐색으로 제거

 

더 이상 입력된 순서가 없으므로 BFS 탐색 순서에 만족! 결과 1 출력

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 그래프의 값을 저장하였습니다.
• 입력한 순서에 따라 BFS탐색이 가능한지 확인하는 bfs함수를 실행하였습니다.
• BFS탐색이 가능하면 1, 가능하지 못하면 0을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 HashSet을 이용해서 지역의 정점을 저장한 뒤 입력된 순서대로 BFS탐색이 가능한지 확인한다.

 

import java.io.*;
import java.util.*;

public class Main{
	static int N;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//그래프 저장 리스트
	static Queue<Integer> result = new LinkedList<Integer>();	//순서 저장 큐
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		for(int i=0;i<=N;i++)
			graph.add(new ArrayList<>());
            	//그래프 저장
		for(int i=0;i<N-1;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		st = new StringTokenizer(br.readLine()," ");
		int size = st.countTokens();
        	//입력되는 순서 저장
		for(int i=0;i<size;i++) 
			result.add(Integer.parseInt(st.nextToken()));
		
		int first = result.poll();	//시작 정점 가져오기
		if(first!=1)	//시작 정점 1이 아니면 BFS 탐색 불가능
			bw.write("0");
		else {
			if(bfs(1))	//입력된 순서 BFS 탐색 시작
				bw.write("1");	//탐색 성공시
			else
				bw.write("0");	//탐색 실패시
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//입력된 순서에 따라 BFS 탐색하는 함수
	static boolean bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		HashSet<Integer> temp = new HashSet<>();	//지역 정점 저장 HashSet
		boolean[] visited = new boolean[N+1];	//정점 방문 여부
		visited[start] = true;
		queue.add(start);
		while(!queue.isEmpty()) {
			int cur = queue.poll();
                   	//인접 정점 저장
			for(int next : graph.get(cur)) {
				if(!visited[next]) {
					temp.add(next);
					visited[next] = true;
				}
			}
			int size = temp.size();
            		//HashSet에 입력되는 순서에 맞게 존재하는지 확인 및 순서에 맞게 BFS탐색 진행
			if(!result.isEmpty()) {
				for(int i=0;i<size;i++) {
					int num = result.poll();
					if(temp.contains(num))
						queue.add(num);
					else		//HashSet에 존재하지 않을 때
						return false;
				}
			}
			temp.clear();
		}
		return true;
	}
}