[KOITP] 그래프 순회

출    처 : http://koitp.org/problem/SDS_PRO_10_1/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1474	222 (15%)	182

문제

그래프에서 탐색을 하는 방법에는 여러 가지가 존재한다. 깊이 우선 탐색(DFS; Depth First Search)과 너비 우선 탐색(BFS; Breadth First Search)가 대표적인 탐색 방법이다. 깊이 우선 탐색과 너비 우선 탐색을 하는 프로그램을 작성하시오.

이 문제에서 너비 우선 탐색이란 큐를 사용하여 한 번에 하나의 정점만 탐색을 하는 형태만을 생각한다.

입력

첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E, 그리고 시작 정점의 번호 S가 공백으로 분리되어 주어진다. (1 ≤ S ≤ V ≤ 20,000, 1 ≤ E ≤ 100,000)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x와 y를 잇는 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y)

출력

첫 번째 줄에 정점 S에서 시작한 깊이 우선 탐색의 결과 중 오름차순으로 가장 빠른 것을 출력한다.

두 번째 줄에 정점 S에서 시작한 너비 우선 탐색의 결과 중 오름차순으로 가장 빠른 것을 출력한다.

힌트

입력 예제 1

5 6 2
1 2
1 3
2 4
3 4
3 5
4 5

출력 예제 1

2 1 3 4 5
2 1 4 3 5

입력 예제 2

5 4 1
1 2
1 3
2 5
3 4

출력 예제 2

1 2 5 3 4
1 2 3 5 4

< Comment >

 딱히 코드상에 바뀐거라고는 Dequeue를 Queue 로 바꾼 것과, Comparator를 재정의 해 준 것 정도뿐인데, 답이 나오니 조금 허무하기도 했습니다. 문제 자체는 그저 DFS와 BFS를 제대로 코드로 구현할 수 있는가 정도를 보는 것입니다. 막상 구현하려고 하다보면 헷갈리기도 하니 의사코드 정도는 암기해 두어도 좋을 것 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class GraphSearch {
	
	public static int V = 0;
	public static int E = 0;
	public static int S = 0;
	
	public static int count = 0;
	
	public static ArrayList<Integer>[] adjust = null;
	public static boolean isVisited[] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		adjust = new ArrayList[V + 1];
		isVisited = new boolean[V + 1];
		
		for (int i = 1 ; i <= V ; i++) {
			adjust[i] = new ArrayList<>();
		}
		
		int node1 = 0;
		int node2 = 0;
		for (int i = 1 ; i <= E ; i++) {
			
			st = new StringTokenizer(br.readLine());
			node1 = Integer.parseInt(st.nextToken());
			node2 = Integer.parseInt(st.nextToken());
			
			adjust[node1].add(node2);
			adjust[node2].add(node1);
		}
		
		for (int i = 1 ; i <= V ; i++) {
			Collections.sort(adjust[i], new Comparator<Integer>() {

				@Override
				public int compare(Integer arg0, Integer arg1) {
					if(arg0 > arg1)		return 1;
					if(arg0 < arg1)		return -1;
					return 0;
				}
				
			});
		}
				
		DFS(S);
		System.out.println();
		Arrays.fill(isVisited, false);
		count = 0;
		BFS(S);
	}
	
	
	public static void DFS(int node) {
		
		if (isVisited[node])	return;
		
		isVisited[node] = true;
		System.out.print(node + " ");
		
		for (int to : adjust[node]) {
			
			if (isVisited[to])	continue;
			DFS(to);
		}		
	}
	

	public static void BFS(int start) {

		Queue<Integer> q = new ArrayDeque<>();
		
		q.add(start);
		while(!q.isEmpty()) {
			
			int node = q.poll();
			if (isVisited[node]) continue;
			
			isVisited[node] = true;
			System.out.print(node + " ");
			
			for (int to : adjust[node]) {
				
				if(isVisited[to])	continue;
				q.add(to);
			}
		}
		
	}
}