[BOJ - JAVA] 1260 - DFS와 BFS(중요)

# 주소

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

1260번: DFS와 BFS

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	static int[][] arr;
	static boolean[] visit;
	static int n;
	static int m;
	static int start;
    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		start = scan.nextInt();
		arr = new int[1001][1001];
		visit = new boolean[1001];
		
		for(int i = 0; i < m; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			arr[x][y] = arr[y][x] = 1;
		}
		dfs(start);
		visit = new boolean[1001];
		System.out.println();
		bfs();
    }
    public static void dfs(int i) {
    	visit[i] = true;
    	System.out.print(i + " ");
    	for(int j = 1; j <= n; j++) {
    		if(arr[i][j] == 1 && visit[j] == false) {
    			dfs(j);
    		}
    	}
    }
    public static void bfs() {
    	Queue<Integer>queue = new LinkedList<Integer>();
    	queue.offer(start);
    	visit[start] = true;
    	System.out.print(start + " ");
    	while(!queue.isEmpty()) {
    		int temp = queue.poll();
    		for(int j = 1; j <= n; j++) {
    			if(arr[temp][j] == 1 && visit[j] == false) {
    				queue.offer(j);
    				visit[j] = true;
    				System.out.print(j + " ");
    			}
    		}
    	}
    }
}

코딩테스트의 단골 기출 문제인 DFS와 BFS입니다.

DFS는 이 블로그에서도 몇 번 다뤘지만 BFS에 대해서는 거의 다룬 적이 없어서 가장 근본인 미로찾기 문제, 노드 연결하기 중 하나를 가져 왔습니다. 다음시간엔 미로찾기 문제를 해보도록 하고 이번에는 노드 연결하기 문제를 다루어 보겠습니다. 

bfs에 대해선 솔직히 구현할 자신이 없었기에 다른 분의 블로그를 참고했는데요. 이 분이 설명을 굉장히 잘해놓으셔서 많이 배웠습니다. 

https://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/729

[실전 알고리즘] 0x05강 - BFS, DFS_구버전

결론적으로 말씀드리자면 dfs는 스택, bfs는 큐를 이용하는 것이 좋습니다.

그리고 방문한 곳과 안한 곳에 대한 구분을 해야하기 때문에 반드시 boolean타입의 visit배열을 꼭 만들어주세요

코드를 살펴보시면 arr, visit, n , m, start를 static하게 선언했습니다.

그리고 2차원 arr에 대해 입력되는 노드들의 행,열 값을 거꾸로 했을때와 직접 놨을 때 모두 1로 저장합니다. 왜냐하면 (1,3)이 입력되면 (3,1)도 1로 들어와야 두 개가 연결이 되겠죠??

그리고 dfs와 bfs를 본격적으로 실행합니다.

dfs라는 것은 깊이 우선 탐색(Depth-First Search)의 약자입니다. 예전 블로그 N과 M(1) 시리즈에서도

https://codingrapper.tistory.com/13

[BOJ - JAVA] 15649 - N과 M 1(백트래킹)

간단하게나마 설명을 했었습니다. DFS는 깊이를 우선적으로 탐색하기 때문에 좌우를 살피기보다 연결이 되어있으면 아래쪽으로 계속해서 내려가며 탐색하는 경향이 있습니다. 한 마디로 '한 우물만 판다' 라고 이해하면 좋을 것 같습니다.

반대로 BFS는 넓이 우선 탐색(Breadth-First Search)의 약자입니다. 표면 그대로 넓이를 우선적으로 탐색하기 때문에 값을 탐색할 때 밑으로 내려가지 않고 양 옆을 우선적으로 탐색하게 됩니다.

이해가 가셨나요?? 코드로 이해하면 조금 더 좋을 것 같네요! 한 번 같이 살펴보겠습니다.

DFS 구문을 한 번 보시겠습니다.

public static void dfs(int i) {
    	visit[i] = true;
    	System.out.print(i + " ");
    	for(int j = 1; j <= n; j++) {
    		if(arr[i][j] == 1 && visit[j] == false) {
    			dfs(j);
    		}
    	}
    }

여기서 입력받는 인자 int i가 들어가게 되면 방문한 값이기 때문에 visit[i] = true로 바꾸어줍니다.

그리고 그것을 제일 먼저 출력하고 한 칸 띄웁니다. 

이후 j = 1부터 2차원 타입의 arr[i][j]이 1이고 방문하지 않은 곳(visit[j] == false)라면 해당 j값을 dfs에 넣고 다시 실행합니다. 이것은 재귀함수로서 계속해서 반복하여 실행되기 때문에 예제1처럼

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

이렇게 입력이 된다면 출력할 땐 1 2 4 3이 출력되는 것입니다. 왜 그럴까요? 

자 1번째 줄에 4 5 1이 입력되었으므로 1이 start값입니다. 그러므로 dfs(start)에는 dfs(1)이 입력됩니다.

이후 (1,2)와 (2,1), (1,3)과 (3,1), (1,4)와 (4,1), (2,4)와 (4,2), (3,4)와 (4,3)은 모두 1로 현재 입력되어 있는 상태죠?

그렇다면 일단 1을 먼저 탐색했으니 이후 dfs내부의 for문을 보시면 j가 1일 땐 방문한 곳이므로 j를 증가시킵니다.

j가 2일 때를 보겠습니다. arr[1][2] == 1이고 visit[2] == false입니다. 그럼 dfs(2)가 실행될 것이고 다시 dfs로 들어와 visit[2] = true가 되고 2를 출력합니다. 이후 다시 for문으로 들어가서 j = 1일 때부터 가동이 되는데, arr[2][1] == 1이면서 visit[j]가 false인 곳을 찾아, 또다시 dfs를 실행하는 것입니다. 

그러므로 1 2 4 3이 순서대로 출력이 되게 됩니다.

 

그럼 BFS를 한 번 살펴보겠습니다.

BFS는 기본적으로 queue를 이용합니다. queue는 선입선출 구조로서 먼저 들어온 데이터가 먼저 나갑니다.

그렇기 때문에 이번 bfs구문에서는 제일 먼저 start값을 queue에 넣는 것은 dfs와 같습니다.

글고 방문한 곳이기 때문에 visit의 해당 인덱스는 true로 바꾸어 줍니다. 그리고 start를 출력하고 그 queue를 비울 때까지 계속해서 while문을 돌리는 것이 핵심입니다.

왜냐하면 bfs는 넓이우선탐색이기 때문에 아래로 내려가기 전, start값 주변의 값 중 탐색할 수 있는지 여부를 먼저 알아야 하기 때문입니다. 그러므로 queue에는 1이 담겨 있다면 1 주위의 값들이 아무 것도 없을 때까지 탐색해야 한다는 것이죠. 그래서 while문 안에 temp = queue.poll()이라고 하면 queue에서 제일 먼저 빠져나갈 값을 temp에 저장 후 해당 arr[temp][j] == 1이고 visit[j] == false(방문하지 않은 값)이면 queue에 j를 넣고 visit[j]도 true로 바고 j를 출력합니다.

그렇게 이 방법을 반복 수행하면

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

이 입력됐을 때 1 2 3 4가 똑같이 출력되는 원리입니다. 그림으로 보실까요?

여기서 O를 1, X를 0이라고 하겠습니다.

(1,1) -> (1,2) -> (1,3) -> (1,4)로 탐색하게 되는 것이 넓이 우선 탐색의 결과입니다.

이해가 가셨나요??

그럼 위의 dfs에선 어떻게 결과가 나올까요?

(1,1) -> (1,2) -> (2,4) -> (4,3)이므로 1,2,4,3이 출력되는 것입니다!

감사합니다.