백준 1260 - DFS 와 BFS (자바 - 그래프)

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

1260번: DFS와 BFS

 

* 문제 요약

그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

정점 번호는 1번부터 N번까지이다.

 

* 입력

첫째 줄에 정점의 갯수 N (1 <= N <= 1,000), 간선의 갯수 M (1 <= M <= 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

어떤 두 정점 사이에 여러개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

* 출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.

V부터 방문된 점을 순서대로 출력하면 된다.

 

* 예시

 

* 해결 과정

그냥 간단한 그래프 탐색 구현문제

입력받은 데이터들을 해시맵에 인접리스트 형태로 저장해준 후 인접리스트로 DFS 알고리즘, BFS 알고리즘을 구현하는 방법 그대로 구현해서 각 탐색 알고리즘의 방문 순서대로 출력시켜주면 끝이다.

단, DFS 알고리즘을 구현할 때 연결된 정점이 여러개인 경우 번호가 가장 작은 정점부터 방문하라고 했는데, DFS 의 경우 스택을 통해 방문이 필요한 정점에 대한 정보를 저장하므로 스택에 정점의 정보를 저장하기 전에 내림차순 형태로 정렬을 해서 스택에 넣어줘야 스택에서 데이터를 꺼낼 때 번호가 가장 작은 정점부터 방문하게 된다는 점을 주의하자.

BFS의 경우엔 방문이 필요한 정점에 대한 정보를 큐에 저장하므로, 큐에 정점의 정보를 저장하기 전에 오름차순 형태로 정렬을 해주면 된다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Main {

	static HashMap<Integer, List<Integer>> hashMap = new HashMap<>();
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		new Main().solution();
	}

	private void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		int v = Integer.parseInt(input[2]);

		for (int i = 0; i < m; i++) {
			input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);

			List<Integer> listA = new LinkedList<>();
			List<Integer> listB = new LinkedList<>();
			if (hashMap.containsKey(a)) {
				listA = hashMap.get(a);
			}
			listA.add(b);
			hashMap.put(a, listA);

			if (hashMap.containsKey(b)) {
				listB = hashMap.get(b);
			}
			listB.add(a);
			hashMap.put(b, listB);
		}

		// DFS 탐색
		visited = new boolean[n + 1];
		Queue<Integer> dfsQueue = dfs(v);
		while (!dfsQueue.isEmpty()) {
			bw.write(dfsQueue.poll() + " ");
		}
		bw.write("\n");
		// BFS 탐색
		visited = new boolean[n + 1];
		Queue<Integer> bfsQueue = bfs(v);
		while (!bfsQueue.isEmpty()) {
			bw.write(bfsQueue.poll() + " ");
		}
		bw.write("\n");
		bw.flush();
		bw.close();
		br.close();
	}

	private static Queue<Integer> bfs(int v) {
		Queue<Integer> visitQueue = new LinkedList<>();
		Queue<Integer> needVisit = new LinkedList<>();

		needVisit.offer(v);

		while (!needVisit.isEmpty()) {
			int number = needVisit.poll();

			if (!visited[number]) {
				visited[number] = true;
				visitQueue.offer(number);

				List<Integer> list = hashMap.get(number);
				if (list != null) {
					Collections.sort(list);
					needVisit.addAll(list);
				}
			}
		}
		return visitQueue;
	}

	private static Queue<Integer> dfs(int v) {
		Queue<Integer> visitQueue = new LinkedList<>();
		Stack<Integer> needVisit = new Stack<>();

		needVisit.push(v);

		while (!needVisit.isEmpty()) {
			int number = needVisit.pop();

			if (!visited[number]) {
				visited[number] = true;
				visitQueue.offer(number);

				List<Integer> list = hashMap.get(number);
				if (list != null) {
					// 연결된 정점이 여러개이면 번호가 가장 작은 정점부터 방문해야 하는데
					// dfs 의 경우 stack 으로 구현되므로 번호가 가장 작은 정점부터 꺼내보게 하려면
					// 내림차순 정렬을 해주어야 한다.
					Collections.sort(list, Collections.reverseOrder());
					needVisit.addAll(list);
				}
			}
		}
		return visitQueue;
	}
}

 

뭐라고 더 설명할 것도 없다. 애초에 문제에서 DFS, BFS 알고리즘으로 탐색한 결과를 순서대로 출력하라고 했으니 그래프 탐색 문제이다.