[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)2178번, 미로 탐색

문제 링크

2178번: 미로 탐색

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 0은 이동할 수 없는 칸, 1은 이동할 수 있는 칸입니다.

2. 1이 인접한 칸으로만 이동할 수 있습니다.

3. 목적지 도착 최소 이동거리를 출력해야 합니다.

 

저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.

미로의 (0, 0)을 기준으로 상, 하, 좌, 우로 탐색을 진행하여 목적지까지 도착하는 최소 이동거리를 구하였습니다.

상, 하, 좌, 우로 탐색하기 위해서

 

dx[] = {-1, 1, 0, 0}

 

dy[] = {0, 0, -1, 1}

 

두 가지 배열을 사용하여 상, 하, 좌, 우로 넓이 탐색을 진행하였습니다.

check배열을 통해서 미로에 해당 지점을 탐색했는지를 확인하였습니다.

예제입력 1에서 미로를 BFS로 진행하는 과정을 보여드리겠습니다.(빨간색은 탐색 완료 지점)

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

(0,0)좌표를 탐색하겠습니다.

저는 상, 하, 좌, 우 순으로 깊이탐색을 진행합니다.

'상'

0 + dx[0] = 0 + (-1) = -1

0 + dy[0] = 0 + 0 =  0

미로의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

'하'

0 + dx[1] = 0 + 1 = 1

0 + dy[1] = 0 + 0 = 0

해당 지점은 1로써 이동할 수 있습니다.

'좌'

0 + dx[2] = 0 + 0 = 0

0 + dy[2] = 0 + -1 = -1

지도의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

'우'

0 + dx[3] = 0 + 0 = 0

0 + dy[3] = 0 + 1 = 1

지도의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

이동할 수 있는 지점이 1개인 경우를 모두 생략하고 2개를 만났을 때를 확인하겠습니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

(0,4)좌표에서 상, 하, 좌, 우로 동일하게 범위 탐색을 진행하면 '상','좌'는 미로에 벗어나기 때문에 하/우를 탐색합니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

범위 탐색을 하기 때문에 (1,4)와 (0,5) 지점에서 모두 범위 탐색을 진행합니다.

(1,4)에서는 상,좌,우는 탐색하지 못하고 '하'만 가능합니다.

(0,5)에서는 상,하,좌,우는 모두 탐색하지 못합니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

(2,4)좌표에서 범위 탐색을 진행하면 '상','좌'는 미로에 벗어나기 때문에 하/우를 탐색합니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

범위 탐색을 하기 때문에 (3,4)와 (2,5) 지점에서 모두 범위 탐색을 진행합니다.

(3,4)에서는 상,하,좌는 탐색하지 못하고 '우'만 가능합니다.

(2,5)에서는 상,하,좌,우는 모두 탐색하지 못합니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

목적지에 도착하면서 현재까지 범위탐색을 진행한 횟수 15를 출력합니다.

 

목적지에 도착했을 때 범위 탐색에 횟수를 결과로 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 미로의 이동 가능 유무를 배열에 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 상, 하, 좌, 우 순으로 탐색을 진행합니다.

3. 목적지에 도착하면 범위 탐색 횟수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 미로 이동 가능 여부를 저장하였습니다.
• 좌표를 저장하는 생성자 coordinate를 만들었습니다.
• BFS을 통해 목적지에 도착하는 이동거리를 구하는 bfs 함수를 만들었습니다.
• BufferedWriter에 목적지 최소 이동거리를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 check[], dx[],dy[],maze[][]와 Queue를 통해 땅을 상,하,좌,우로 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//-------좌표 저장할 생성자--------
	public static class coordinate{	
		int x,y;
		public coordinate(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}
	}
	public static int N,M;
	public static int[][] maze;		//미로 이동유무 저장 배열
	public static boolean[][] check;	//미로 탐색 확인 배열
	public static int[] dx = {-1, 1, 0, 0};		//상,하,좌,우 X값 변경
	public static int[] dy = {0, 0, -1, 1};		//상,하,좌,우 Y값 변경
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화----------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	maze = new int[N][M];
    	check = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		String temp = br.readLine();
    		for(int j=0;j<M;j++) {
    			maze[i][j] = Character.getNumericValue(temp.charAt(j));
    		}
    	}
    	int result = bfs();		//bfs함수 실행 및 범위 탐색 횟수 저장
    	bw.write(result + " ");		//탐색 횟수 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //-------BFS를 이용한 목적지 이동 거리 구하는 함수--------
    public static int bfs() {
    	int count = 0;		//이동 거리
    	Queue<coordinate> queue = new LinkedList<coordinate>();	//탐색 기준 지점 저장 큐
    	check[0][0] = true;	
    	queue.add(new coordinate(0,0));		//(0,0) 지점 시작
    	boolean arrive = false;		//목적지 도착여부
    	while(!queue.isEmpty()) {
    		count++;		//이동 거리 + 1
    		int size = queue.size();
    		for(int i=0;i<size;i++) {		//현재 범위 탐색 가능한 기준 모두 탐색
        		coordinate temp = queue.poll();
        		int x = temp.getX();
        		int y = temp.getY();
        		if(x == N-1 && y==M-1) {	//목적지 도착
        			arrive = true;
        			break;
        		}
                    //상,하,좌,우으로 범위 탐색
        		for(int j=0;j<4;j++) {
        			int tempX = x + dx[j];	//상,하,좌,우 X값 변경
        			int tempY = y + dy[j];	//상,하,좌,우 Y값 변경
        			if(tempX>=0 && tempX<N && tempY>=0 && tempY<M && maze[tempX][tempY]==1) {
        				if(!check[tempX][tempY]) {
        					check[tempX][tempY] = true;
        					queue.add(new coordinate(tempX, tempY));
        				}
        			}
        		}
    		}
    		if(arrive)		//목적지 도착시
    			break;
    	}
    	return count;
    }
}