DFS 와 BFS 는 대표적인 탐색알고리즘이다.
DFS 는 스택과 재귀함수를 사용해서 구현 할 수있고
BFS 는 큐를 사용해서 구현한다.

이제 실전문제를 확인해보자.

실전문제 음료수 얼려먹기

문제요약:
N,M을 입력받아 N*M 크기의 배열에 0과1을 입력받습니다. 이때 1은 칸마기를 의미하고 0은 공간은 나타냅니다. 이때 총 구간의 수를 구하는 문제입니다.

이 문제는 대표적인 탐색알고리즘 문제이다.
BFS,DFS 다 사용할 수있지만 , 나는 BFS 알고리즘을 사용해서 구현 해보았다.

구현코드:

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

class Node{
	int x, y;
	Node(int x,int y){
		this.x = x;
		this.y = y;
	}
}

public class Main{
	
	static int[][] cover;
	static int[][] visited;
	static int n ,m , cnt =0;
	static int []dx = {0 ,0 ,-1 ,1};
	static int []dy = {1 ,-1 ,0 ,0};
	static Queue<Node>queue;
	public static void bfs(int x ,int y) {
		queue = new LinkedList<>();
		queue.add(new Node(x,y));
		visited[x][y] = 1;
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if(cover[nx][ny] == 0 && visited[nx][ny] == 0) {
					queue.add(new Node(nx,ny));
					visited[nx][ny] = 1;
				}
			}
		}
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		cover = new int[n][m];
		visited = new int[n][m];
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			for(int j = 0; j < m ; j++) {
				cover[i][j] = str.charAt(j) -'0';
			}
		}
		for(int i = 0;i < n ; i ++) {
			for(int j = 0; j < m; j++) {
				if(cover[i][j] == 0 && visited[i][j] == 0) {
					bfs(i,j);
					cnt ++;
				}
			}
		}
		System.out.println(cnt);
		
		
	}
}

코드해석:
우선 입력받는건 넘어가고 bfs 에 대해서 알아봅시다. bfs 란 인접노드 를 먼저 검사하고 그다음 그다음을 확인 합니다. 그래서 queue 를 사용하여 구현하는데 저도 bfs를 처음접했을 때 머리를 싸맨 기억이있습니다. 하지만 한번 구조를 파악하게 되면 쉽게 느껴집니다. 우선 배열값과 방문여부를 체크 합니다. 그리고 둘다 조건에 맞을경우 bfs 함수를 실행하는데 bfs 함수는 다음과 같습니다.
우선 queue에 값을넣고 while문을 실행시켜 queue 가 전부다 비었을때 까지 반복해줍니다. 이때 Node라는 class 를 만들어서 x y 값을 저장해주는게 편해서 해보았습니다. 이때 중요한 것은 문제에서 상하좌우가 붙어있경우라고 표시해주었기 때문에 for 문을 4번 돌아줍니다. 그리고 상하좌우를 이동할때 틀에서 벗어나는것이 아닌지 확인해줍니다. 그리고 조건에 맞다면 다시 큐에 add 해주는 것이 포인트 입니다.

실전문제 2.미로찾기

문제요약:
N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력
첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력
첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시
10

구현코드:

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

class Node{
	int x, y;
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class main2 {
	
	static int[][] map;
	static int n ,m ,x ,y;
	static int[] dx = {0 ,0 ,-1 ,1};
	static int[] dy = {1 ,-1 ,0 ,0};
	static Queue<Node>queue;
	public static void bfs(int x ,int y) {
		queue = new LinkedList<>();
		queue.add(new Node(x ,y));
		while(!queue.isEmpty()){
			Node node = queue.poll();
			for(int i = 0 ; i < 4 ;i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >= n || ny <0 || ny >= m) continue;
				if(map[nx][ny] == 0) continue;
				if(map[nx][ny] == 1) {
					queue.add(new Node(nx,ny));
					map[nx][ny] = map[node.x][node.y] + 1;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map =new int[n][m];
		for(int i = 0 ;i < n; i++) {
			String str = br.readLine();
			for(int j = 0 ; j < m; j++) {
				map[i][j] = str.charAt(j) -'0';
			}
		}
		bfs(0,0);
		System.out.println(map[n-1][m-1]);
	}
}

코드해석: 미로탈출 문제는 전형적인 bfs 문제이다. 왜냐하면 우리는 최단거리를 구할 것이기 때문에 인접한 값으로 이동하는 방법이 필요하다. 그림으로 이해해보자.

그림은 :https://blog.hexabrain.net/269 이블로그 에서 퍼왔다.
1이 시작점이라고 생각해보자. 음료수 얼리기문제와 다른점음 음료수 얼리기는 구간이 다 나누어 져있어서 bfs 함수를 계속 호출해야했지만 , 미로탈출문제는 연결되어있기 때문에 한번만 호출해도 된다는점이다.
다시 그림으로 돌아와서 3에서 4로 가는 부분이있다.양갈래로 나누어지는데 우리는 3과 인접한 노드를 찾을 찾을 때 갈 수있는 경로를 이전 노드 값 +1 씩 해주면 된다. 그리고 queue 에넣고 빼고를 반복하여 이전노드 값 +1 을 해주면 되는 것이다.