[JAVA] DFS와 BFS의 기본 형태

- DFS와 BFS와 for문은 모두 완전탐색을 위한 것이다.

용도에 따라 선택하면 된다

 

1. DFS - 모든 경우의 수를 다 봐야할때, 하나의 경우의 수를 끝까지 깊게 다 본다음에 바로 전 노드를 보는 형태

            (시작점에 따라 형태가 조금씩 다름- 1개면 0,0부터, 여러곳마다 시작해야하면 for문 안에 dfs함수 넣는방식) 

2. BFS - 모든 경우의 수를 다 봐야할때, 조건을 만족하면 바로 나감 (return OR system.exit)

3. for - 제약조건이 많지 않은경우 사용

 

 

------------------------------------------------------------------------------------------------

EX) 0.0에서 시작하여 1이 있는 곳으로 갈때 최단루트를 구하기

단, 방향은 동,서,남,북으로 밖에 못가고 한번 지나간 좌표는 다시 들를 수 없다.

 

6 5 // 행,열  
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 1 
0 0 0 0 0 // 행,열에 맞는 좌표값 제공

 

1. DFS로 봤을때의 흐름

DFS는 재귀함수를 사용한다.

0.0에서 시작을 하면, 먼저 동/서/남/북 방향으로 한칸씩 이동한다.

0.0에서 총 4번의 경우의 수를 도는데, 동쪽으로 가서 0.1로 가게 된다면 0.1에서 또다시 동/서/남/북 방향으로 한칸씩 이동해본다. 모든 경우의 수를 보는 것

 

(1) 0.0에서 북 방향으로 이동

0.0에서 북방향으로 이동하면 배열의 범위를 벗어나므로 끝난다. 다른 방향을 계속해서 보기위하여 continue; 사용

 

(2) 0.0에서 동 방향으로 이동

0.0에서 동방향으로 이동하면 0.1이 된다. 그럼 0.1에서도 또다시 4번의 방향을 돌면서 이동을 수행한다.

이때 한번 들렸던 곳인지 check해서 빠져나올 수 있도록 한다.

 

(3),(4) 서,남 방향도 동일

 

--> 현재 노드를 탐색하다가 불가능해지면 그 바로 전 노드를 다시 탐색하는 방식이다.

 

 

2. BFS로 봤을때의 흐름

BFS는 Queue를 이용한다. 

큐에다가 처음 시작점에 대한 정보를 넣어두고, 큐가 전부 비워질 때까지 while문이 돌면서 큐에 들어간 것을 하나씩 빼서 그 위치를 기준으로 4방향 이동한 값을 다시 큐에 넣는다. 

(0) 큐에 시작점인 {0.0} 정보와 cnt값을 넣는다. (현재 큐 : {0.0},0 )

(1) 큐에 들어간 것을 하나 뺀다. {0.0} 기준 동,남 방향으로 이동이 가능해서 해당 방향으로 이동한 좌표와 cnt 값을 큐에 넣어준다. (현재 큐 : {0.1},1 / {1.0},1 )

(2) 동쪽 방향부터 돌아서 {0.1}부터 큐에 들어갔다고 치자. 방향을 다돌았기 때문에 다시 맨앞의 큐를 하나 뺀다.

{0.1}이다. {0.1} 기준으로 4가지 방향으로 또 for문을 돌린다. (현재 큐 : {1.0},1 / {0.2},2 / {1,1},2 )

(3) 방향을 다 돌았기 때문에 맨 앞의 큐를 하나 뺀다. 

{1.0}이다. {1.0} 기준으로 4가지 방향으로 또 for문을 돌린다. 이 때, {1.1}처럼 {0.1}에서 이미 들려버린 좌표가 있다.

이 경우에는 먼저 들렸던 {0.1}에서 visit 처리를 해줬기에 visit 방문 check만해서 중복으로 큐에 들어가지 않도록 처리한다. (현재 큐 : {0.2},2 / {1,1},2 / {2,0},2)

(4)...(n) 이런식으로 해당 좌표의 값이 map[row][col] ==1이 나오면 도착한 것으로 보고 cnt값을 ans에 넣어준다. 

cnt가 경로이다. 그리고 값을 찾았기 때문에 return하여 종료한다.

package algorithm;

import java.util.*;
import java.io.*;

class Position{ //클래스 구조체
	int row, col,cnt;
	boolean wall;
	public Position(int row, int col,int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
	}
}
public class dfsTest {
	public static final int[] dx = {-1,0,1,0}; //난 이 숫자를 절대로 바꾸징낳겠다.
	public static final int[] dy = {0,1,0,-1}; //북동남서
	private static final int LinkedList = 0;
	public static int map[][];
	public static boolean visit[][];
	public static int ans = Integer.MAX_VALUE;
	public static int N,M;
	public static Queue<Position> q; //row, col좌표만 
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("Test4.txt"));
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new int[N][M];
		visit = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; 
					j++) {
				map[i][j] = sc.nextInt();
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dfs(i,j,0); //16번
			}
		}
		dfs(0,0,0);
		bfs();
		
		System.out.println(ans);
		
		
		
	}
	public static void dfs(int row ,int col,int cnt) {
		//1.종료조건
		if(map[row][col] == 1) {
			ans = Math.min(cnt, ans); //경로중에 최솟값
			return;
		}
		
		//2. 방향탐색
		for (int i = 0; i < 4; i++) { //북동남서
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			//예외처리
			if(nx < 0 || nx >= N || ny < 0 || ny >=M) {
				//ㅃ나갓을경웅
				continue;
			}
			//방문처리
			if(visit[nx][ny]) {
				continue;
			}
			visit[row][col]= true; //방문 했다.
			dfs(nx,ny,cnt+1); 
			visit[row][col]= false; //방문 했다.
		}
	
	}
	public static void bfs() { //1번
		q = new LinkedList<>();
		
		//어디부터 시작할 것인가.
		q.add(new Position(0,0,0)); //시작 좌표가 들어가.
		//q.add(new Position(5,5,0)); //시작 좌표가 들어가. 시작좌표가 여러개일경우(==동시에 뿌려주려고 할때)
		 
		while(!q.isEmpty()) { //q가 빌때까지 (여행이 종료될 때까지)
			Position pos = q.poll();			
			//2. 방향탐색
			for (int i = 0; i < 4; i++) { //북동남서
				int nx = pos.row + dx[i];
				int ny = pos.col + dy[i];
				
				//예외처리
				if(nx < 0 || nx >= N || ny < 0 || ny >=M) {
					//ㅃ나갓을경웅
					continue;
				}
				//방문처리
				if(visit[nx][ny]) {
					continue;
				}

				visit[nx][ny]= true; //방문 했다.
				//종료조건은 어디서 해야할까
				if(map[nx][ny] == 1) { //집어넣을곳이 1이다!
					ans = pos.cnt+1;
					return;
				}
				//q에 넣을 수 있는 친구들만 남는다.
				q.add(new Position(nx,ny,pos.cnt + 1));
				
				//혹은 동시에 퍼져나가기
			}
		}
	}
}