[백준알고리즘-JAVA]1260번 풀이(DFS와 BFS) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1260번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1260 (DFS와 BFS)

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다

출력

첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

입력, 출력 예제

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static boolean[] check;
	static int[][] arr;
	
	static int node, line, start;
	
	static Queue<Integer> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}
			//sb.append("\n");
			dfs(start);
			sb.append("\n");
			check = new boolean[node+1];
			
			bfs(start);
			
			System.out.println(sb);
		
		}
	public static void dfs(int start) {
		
		check[start] = true;
		sb.append(start + " ");
		
		for(int i = 0 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i])
				dfs(i);
		}
		
	}
	
	public static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			
			start = q.poll();
			sb.append(start + " ");
			
			for(int i = 1 ; i <= node ; i++) {
				if(arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
		
		
	}

}

DFS와 BFS 정말 유명한 알고리즘이지만 저는 처음 접해보았습니다. 뭐 기본적으로 DFS와 BFS가 무슨 의미를 갖는지는 알고 있었죠. 이번에 알고리즘으로 다시 풀어보면서 느꼈지만 DFS는 스택, 재귀 BFS는 큐를 활용하여 구현한다는 것을 알 수 있었습니다. 정확한 구현 법은 STEP을 따라가며 이해해보도록 하죠

---

알고리즘 흐름도

 

---

STEP1 문제의 이해

 문제의 이해는 아주 간단하다 DFS 즉 깊이 우선으로 탐색하는 방법과 BFS로 탐색한 결과를 출력하면 되는 문제이다.

 

여기서 DFS란 깊이 우선 탑색으로 예제 1번으로 들어보자

1 2

1 3

 1 4

2 4

3 4

 

가 들어왔는데 처음으로 1 2가 들어오면 우리는 그다음으로 2 4 그다음 이어지는 곳이 없으니 다시 1 3 3 4 또 이어지는 곳이 없으니 1 4 이런 식으로 탐색이 되는 것입니다.

 

BFS라면 넓이 우선 탐색이니 당연히

 

1 2

1 3

1 4

2 4

3 4

이런 식으로 탐색이 될 것입니다.

---

STEP2 입력받기

		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}

입력받기란 뭐... 어려울 게 없습니다. 단 arr이 무엇인지 궁금해하시는 분들이 있으실 겁니다. 바로 노드 간의 간선을 표현해 주기 위한 표이죠.

	1	2	3	4
1		1	1	1
2	1			1
3	1			1
4	1	1	1

이런 식으로 말이죠 (입력 예제 1번 활용) 이러한 방법을 인접 행렬 방법이라고도 하네요

 

따른 방법은 인접 리스트를 활용한 방법이 있기도 합니다.

1번 노드 ->

3

2

4

2번 노드 ->

4

3번 노드 ->

4

4번 노드 ->

2

3

 

그런다 해당 문제에서는 숫자가 낮은 노드부터 탐색하려고 하니, 해당 방법은 또 따른 정렬을 통해 탐색해야 될 듯싶네요

---

STEP 3 DFS 구현하기

	public static void dfs(int start) {
		
		check[start] = true;
		sb.append(start + " ");
		
		for(int i = 0 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i])
				dfs(i);
		}
		
	}

DFS구현은 재귀를 활용하는 방법을 사용하였습니다. (스택도 있지만, 보다 간편한 방법으로 구현해보았습니다.)

 

이번 DFS를 보면 시작점을 줍니다. 그 시작 접을 CHECK BOOLEAN배열을 통해 체크해 줍니다. 

 

재귀를 통해서 만약 arr이 ==1이라면 간선이 있다는 표시겠죠? 그다음 check가   false라면 탐색하지 않았던 노드를 의미하고요.

 

또한 for문은 0부터 시작하기에 해당 노드에 거리게 되면 dfs(i)로 더 깊이 즉 DFS가 바로 실행이 먼저 되게 됩니다.

 

FOR문이 끝마치기 전에 DFS를 먼저 끝낸다.!

---

STEP 4 BFS 구현하기

 사실 저는 BFS를 구현하기가 가장 까다로웠습니다. 흠.. 큐를 잘못 생각해버려서죠..

	public static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			
			start = q.poll();
			sb.append(start + " ");
			
			for(int i = 1 ; i <= node ; i++) {
				if(arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}	
	}

큐 또한 시작 노드를 받아줍니다. 큐에는 해당 노드를 넣어준 뒤 탐색을 시작합니다.

 

큐의 처음 삽입한 노드를 빼주고 그 노드와 연결되어있는 (ARR 배열) 노드들을 탐색하여 Q에 넣습니다. 이와 같은 경우 DFS와 는 다르게 처음 노드와 연결된 넓이 노드부터 Q에 들어가는 것을 알 수 있죠.

 

이러한 큐를 반복해서 꺼내 주다가 큐가 비어지면 끝!!

 

(사실 큐의 FIFO와 덱 큐의 LIFO를 순간 착각해서.... 오래 걸렸던 문제였던 것 같습니다...)

 

사실 이리 보면 DFS BFS는 단지 무엇을 먼저 찾을지가 관건인 거 같긴 한다. 다른 DFS와 BFS문제를 풀어보니 좀 더 각 기법에 맡는 문제들이 있어 보입니다. 

 

이러한 문제들을 더 풀어보면서 DFS와 BFS에 대한 감을 익혀보도록 하겠습니다.