[BaekJoon] 1260 DFS와 BFS

1.  문제 링크

2.  문제

요약

• 그래프의 정점과 간선이 주어졌을 때, BFS와 DFS로 방문한 순서를 출력합니다. 만약 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문합니다.
• 입력: 첫 번째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어지고 두 번째 줄부터 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어집니다.
• 출력: 첫 번째 줄에는 DFS를 수행한 결과, 두 번째 줄에는 BFS를 수행한 결과를 출력합니다.

설명

DFS(Depth-First Search)

깊이 우선 탐색이란

• 루트 노드(혹은 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐핵하고 넘어가는 방법입니다.
• 즉, 정점의 자식들을 먼저 탐색하는 방식입니다.
• 모든 노드를 방문하고자 할 때 이 방법을 사용합니다.
• 단순 검색 속도는 BFS보다 느리지만 BFS보다 간단합니다.

BFS(Breadth-First Search)

너비 우선 탐색이란

• 루트 노드(혹은 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다.
• 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효율적으로 해결할 수 있습니다.
• DFS에 비해 단순 검색 속도가 빠르고 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public ArrayList<Integer> DFS(int start, HashMap<Integer, ArrayList<Integer>> graph) {
		ArrayList<Integer> visited = new ArrayList<Integer>();
		ArrayList<Integer> needVisit = new ArrayList<Integer>();
		needVisit.add(start);
		while(needVisit.size() > 0) {
			int node = needVisit.remove(0);
			if(!visited.contains(node)) {
				visited.add(node);
				needVisit.addAll(0, graph.get(node));
			}
		}
		
		return visited;
	}
	
	public ArrayList<Integer> BFS(int start, HashMap<Integer, ArrayList<Integer>> graph) {
		ArrayList<Integer> visited = new ArrayList<Integer>();
		ArrayList<Integer> needVisit = new ArrayList<Integer>();
		needVisit.add(start);
		while(needVisit.size() > 0) {
			int node = needVisit.remove(0);
			
			if(!visited.contains(node)) {
				visited.add(node);
				needVisit.addAll(graph.get(node));
			}
		}
		
		return visited;
	}
	
	public HashMap<Integer, ArrayList<Integer>> makeGraph(int vertex, ArrayList<String> edges) {
		HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> each_edge = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < vertex; i++) {
			each_edge.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < edges.size(); i++) {
			StringTokenizer st = new StringTokenizer(edges.get(i));
			int vertex1 = Integer.parseInt(st.nextToken());
			int vertex2 = Integer.parseInt(st.nextToken());
			each_edge.get(vertex1 - 1).add(vertex2);
			each_edge.get(vertex2 - 1).add(vertex1);
		}
		for(int i = 0; i < each_edge.size(); i++) {
			Collections.sort(each_edge.get(i));
			graph.put(i + 1, each_edge.get(i));
		}
		return graph;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int vertex = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		ArrayList<String> edges = new ArrayList<String>();
		for(int i = 0; i < edge; i++) {
			edges.add(br.readLine());
		}
		br.close();
		Main m = new Main();
		HashMap<Integer, ArrayList<Integer>> graph = m.makeGraph(vertex, edges);
		ArrayList<Integer> dfs = m.DFS(start, graph);
		for(int i = 0; i < dfs.size(); i++) {
			bw.write(dfs.get(i) + " ");
		}
		bw.write("\n");
		ArrayList<Integer> bfs = m.BFS(start, graph);
		for(int i = 0; i < bfs.size(); i++) {
			bw.write(bfs.get(i) + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 우선 간선이 연결하는 두 정점이 주어지기 때문에 이를 이용하여 그래프를 만듭니다.
• 그래프를 만들 때에는 HashMap을 이용하여 각 정점에 연결되어 있는 정점들을 저장해놓습니다. 그리고 정점 번호가 낮은 순으로 방문해야 하므로 연결되어 있는 정점들의 리스트를 오름차순으로 정렬해놓습니다.
• DFS를 진행할 때에는 시작 정점과 그래프를 이용하여 구합니다.
1. DFS를 진행할 때에는 이미 방문한 정점을 저장할 수 있는 ArrayList와 방문이 필요한 정점을 저장하는 ArrayList를 만듭니다.
2. 시작 노드는 처음에 방문해야 하기 때문에 우선 방문이 필요한 정점을 저장하는 ArrayList에 넣어놓습니다.
3. 방문이 필요한 정점에서 가장 앞에 있는 정점이 먼저 방문해야 하는 정점이므로 해당 정점을 방문이 필요한 정점에서 지운 후에 해당 정점이 방문한 정점을 저장하는 ArrayList에 존재한다면 이미 방문한 노드이므로 다른 작업은 하지 않습니다.
4. 만약 존재하지 않는다면 지운 노드를 방문한 정점을 저장하는 ArrayList에 넣어놓고 해당 노드에 연결되어 있는 노드를 모두 방문이 필요한 정점을 저장하는 ArrayList에 가장 앞에 넣습니다.
5. 3번부터 4번까지 반복하여 방문이 필요한 정점을 저장하는 ArrayList가 비워지면 탐색이 끝납니다.
• BFS를 진행할 때에는 시작 정점과 그래프를 이용하여 구합니다.
1. DFS와 마찬가지로 이미 방문한 정점을 저장할 수 있는 ArrayList와 방문이 필요한 정점을 저장하는 ArrayList를 만듭니다.
2. 시작 노드는 처음에 방문해야 하기 때문에 우선 방문이 필요한 정점을 저장하는 ArrayList에 넣어놓습니다.
3. 방문이 필요한 정점에서 가장 앞에 있는 정점이 먼저 방문해야 하는 정점이므로 해당 정점을 방문이 필요한 정점에서 지운 후에 해당 정점이 방문한 정점을 저장하는 ArrayList에 존재한다면 이미 방문한 노드이므로 다른 작업은 하지 않습니다.
4. 만약 존재하지 않는다면 지운 노드를 방문한 정점을 저장하는 ArrayList에 넣어놓고 해당 노드에 연결되어 있는 노드를 모두 방문이 필요한 정점을 저장하는 ArrayList에 넣습니다.
5. 3번부터 4번까지 반복하여 방문이 필요한 정점을 저장하는 ArrayList가 비워지면 탐색이 끝납니다.