백준 1260. DFS와 BFS(JAVA)

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static int n , m , v; // 정점, 간선, 시작 정점
	static int[][] graph; //
	static boolean Visit[]; // 방문하였는지 확인하기 위해 
	static Stack<Integer> st = new Stack<>();
	static Queue<Integer> q = new LinkedList<>();	
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		v = sc.nextInt();
		graph = new int[n+1][n+1]; // 좌표를 그대로 받아들이기 위해 +1 해서 .... 
		Visit = new boolean[n+1]; // false로 초기화함. 
		
		for(int i = 1 ; i <= m ; i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			graph[tmp1][tmp2] = 1;
			graph[tmp2][tmp1] = 1;
		}
		
		DFS(v);
		Visit = new boolean[n+1];
		System.out.println();
		BFS(v);
	}
	
	public static void DFS(int v) { // 재귀함수를 활용해서
		st.push(v);
		Visit[v] = true;
		while(!st.empty()) {
			int pt = st.pop();
			System.out.print(pt + " ");
			for(int i = 1 ; i <= n ; i ++) {
				if(graph[pt][i] ==1 && !Visit[i]) {
					DFS(i);
				}
			}
		}
	}
	
	public static void BFS(int v) { // 큐를 활용해서 
		q.add(v);
		Visit[v] = true;
		while(!q.isEmpty()) {
			int pt = q.poll();
			System.out.print(pt + " ");
			for(int i = 1 ; i <= n ; i++) {
				if(graph[i][pt] == 1 && !Visit[i] && i!= pt) {
					q.add(i);
					Visit[i] = true;				
				}
			}
		}
	}
}

○ 문제 요약

DFS와 BFS를 수행한 결과를 방문한 순서대로 출력해라.

문제를 풀기에 앞서 DFS와 BFS에 대한 기본 지식이 필요하다. 

DFS란? (깊이 우선 탐색, Depth-First Search)

=> 말 그대로 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없으면 옆으로 이동한다.

1. 모든 노드를 방문하고자 하는 경우 이 방법을 선택함.
2. 깊이 우선 탐색이 너비 우선 탐색보다 간단함.
3. 검색 속도 자체는 너비 우선 탐색에 비해 느림. 
4. 스택 또는 재귀 함수로 구현 

 

BFS란? (너비 우선 탐색, Breadth-First Search)

=> 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다. 
큐를 이용해서 구현 
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 3번 행동한다.
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 
남기고 해당 칸을 큐에 넣는다.
4. 큐의 모든 원소가 빌 때까지 2를 반복한다.

 

○ 문제 풀이

예제 입력 1을 기준으로 문제를 풀이하려고 한다. 위 입력을 그림으로 표현하면 오른쪽과 같은 모습을 보인다. 

문제에서 주어진 간선은 양방향이라고 했으므로 양방향 화살표로 표시를 했다.

int n , m , v는 차례대로 정점의 개수, 간선의 개수, 시작할 정점의 번호를 의미한다.

int [][] graph는 간선의 연결 상태를 입력하기 위해 선언했다.

boolean Visit []는 해당 정점을 방문했을 때 방문했다는 표시를 하기 위해 선언했다.

Stack <Integer> st는 DFS를 구현하기 위한 것이고 Queue <Integer> q는 BFS를 구현하기 위해 선언했다.

여기서 graph 2차원 배열을 만드는데 크기를 n+1로 한 이유는 좌표를 그대로 받아들이기 위함이다.

마찬가지로 Visit 1차원 배열도 좌표를 그대로 받아들이기 위해 n+1 크기로 만들고 해당 배열은 현재 False로 되어 있다.

for문으로 들어와서 간선을 입력해주는데 3줄과 4줄을 한 이유는 양방향 간선이기 때문이다.

graph에 원하는 대로 입력이 되었는지 확인을 해보면 아래와 같다.                                    

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

위 그림에 대한 잠깐 설명을 하면 입력을 받을 때 (1,2) (1,3) (1,4) (2,4) (3,4)가 연결되도록 입력을 받았다. 그림을 보면 해당 좌표에 맞게 1을 넣어 연결이 되었다는 표시를 하였고 양방향 간선이기 때문에 그 반대의 경우도 1을 넣었다.

DFS 메서드는 시작 정점 숫자를 변수로 받는다. 받은 숫자를 Stack에 넣고 Visit [v]에 true를 대입하여 해당 정점에 방문했다는 사실을 표시한다.

while문은 Stack 안에 값이 있으면 계속 수행을 하는데 Stack에 있는 정점을 빼서 출력을 해준다.

---

DFS 실행 과정 

DFS(1) 실행 -> 1 출력 -> for문에서 i가 2일 때 조건 충족 -> DFS(2) 호출

DFS(2) 실행 -> 2 출력 -> for문에서 i가 4일 때 조건 충족 -> DFS(4) 호출

DFS(4) 실행 -> 4 출력 -> for문에서 i가 3일 때 조건 충족 -> DFS(3) 호출

DFS(3) 실행 -> 3 출력 -> for문에서 n까지 수행 후 Stack이 empty이므로 while문 탈출 -> 1 2 4 3 결과 출력

---

BFS 실행 과정

BFS(1) 실행 -> 1 출력 -> for문에서 i = 2일 때 조건 충족 -> q.add(2) 실행하고 Visit [2] = true 넣어서 2번 방문 확인 

-> i = 3 일 때 q.add(3) 실행하고 Visit [3] = true 넣어 3번 방문 확인 -> i = 4 일 때 q.add(4) 실행하고

Visit [4] = true 넣어 4번 방문 확인 -> for문 탈출하면 현재 Queue에는 [ 2, 3, 4]가 들어있고 Queue가 빌 때까지 while문 수행 -> 1 2 3 4 결과 출력   

 

DFS(v) => 1 2 4 3 

Visit를 초기화한 이유는 DFS를 실행하면서 true가 되었기 때문에 BFS를 위해 false로 초기화한 것.

BFS(v) => 1 2 3 4 

○ 결과