[백준알고리즘-JAVA]2178번 풀이(미로탐색) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2178번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2178 (미로 탐색)

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

입력, 출력 예제

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static boolean[][] check;
	static int[][] arr;
	static int[] moveX = {0, 0, 1, -1};
	static int[] moveY = {1, -1, 0, 0};

	static int count = 0,ans = Integer.MAX_VALUE;

	static int N, M;
	static StringBuilder sb = new StringBuilder();

	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());
		
		arr = new int[N][M];
		check = new boolean[N][M];
		
		for(int i = 0 ; i < N ; i++) {
			String str = br.readLine();
			char[] ch = str.toCharArray();
			
			for(int j = 0 ; j < ch.length ; j++) {
				arr[i][j] = Character.getNumericValue(ch[j]);
			}
		}
		check[0][0] = true;
		bfs(0,0);
			
			System.out.println(arr[N-1][M-1]);
		}

	public static void bfs(int x, int y) {
		Queue<spot> q = new LinkedList<>();
		q.add(new spot(x,y));
		
		while(!q.isEmpty()) {
			spot s = q.poll();
			for (int i = 0; i < 4; i++) {
                int nextX = s.x + moveX[i];
                int nextY = s.y + moveY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                if (check[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }
                q.add(new spot(nextX, nextY));
                arr[nextX][nextY] = arr[s.x][s.y] + 1;
                check[nextX][nextY] = true;
            }
		}
	}

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

사실 BFS와 DFS문제를 풀어보면서 어느 정도 풀 수 있다고 자신했지만, 이번 문제를 보고 아직 정확히 이해하지 못하고 있음을 실감했다. 네 맞습니다... 어려웠습니다. ㅋㅋㅋ 

 

그래도 다른 분들의 코드를 참고해서 문제에 대한 이해는 끝난 상태이죠. 이게 왜 BFS인지도 이해가 가기도 했고요. 이제 STEP을 따라 문제의 이해를 해보도록 하죠

---

알고리즘 흐름도

 입력받기 -> 초기 check 설정하기 -> bfs 구현하기 -> 출력하기

---

STEP1 입력받기 및 초기 check 설정하기

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		check = new boolean[N][M];
        
		for(int i = 0 ; i < N ; i++) {
			String str = br.readLine();
			char[] ch = str.toCharArray();
			
			for(int j = 0 ; j < ch.length ; j++) {
				arr[i][j] = Character.getNumericValue(ch[j]);
			}
		}
		check[0][0] = true;

입력받는 거야 뭐.. 받으라는데로 받으면 끝! 여기서 초기 check설정이란 0,0부터 시작하니 해당 check를 true로 해주라는 의미였습니다!

---

STEP2 BFS 구현하기

 사실 이번 문제의 핵심이죠 동서남북을 지나면서 1이 된 칸만 지나갈 수 있도록 해주면 됩니다. 이때 저희는 각 지점을 확인할 수 있는 CLASS를 하나 설정할 것입니다~

	public static void bfs(int x, int y) {
		Queue<spot> q = new LinkedList<>();
		q.add(new spot(x,y));
		
		while(!q.isEmpty()) {
			spot s = q.poll();
			for (int i = 0; i < 4; i++) {
                int nextX = s.x + moveX[i];
                int nextY = s.y + moveY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                if (check[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }
                q.add(new spot(nextX, nextY));
                arr[nextX][nextY] = arr[s.x][s.y] + 1;
                check[nextX][nextY] = true;
            }
		}
	}
    
    class spot{
	int x;
	int y;
	spot(int x, int  y){
		this.x = x;
		this.y = y;
	}
}

처음 좌표 0,0부터 시작합니다. q를 하나 생성한 후 q에 입력으로 받은 0,0부터 시작 함을 알립니다.

 

 - while문으로 큐가 비어있을 때까지 반복합니다.

 - spot 인스턴스를 q에 있는 0,0으로 만들어 줍니다.

 - 이제 큐에서 빼온 s를 동서남북으로 확인해 줍니다.

 - 만약 범위가 주어진 범위보다 넘어가면 continue를 통해 다음 방향(동서남북)으로 전환해 줍니다.

 - 만약 이미 방문했거나 해당 방향의 값이 0이라면 continue를 통해 다음 방향으로 전환해 줍니다.

 - 이 모든 if문을 통과했다면, q에다가 해당 좌표를 추가해 줍니다. 그리고 해당 arr 값에 +1을 해줍니다.

 - 또한 그 좌표를 방문했다는 의미인 check를 true로 바꿔줍니다.

 

이러한 과정을 모두 마치면 아래와 같이 표가 나오게 됩니다. (입력 예시 1)

1	0	9	10	11	12
2	0	8	0	12	0
3	0	7	0	13	14
4	5	6	0	14	15

 이런 식으로 arr이 채워지게 됩니다. 그렇게 되면 결국 마지막 배열인 15가 답이 되게 되겠죠!

대부분의 모든 미로 문제는 이러한 bfs를 통해 산출하게 됩니다. 물론 얼마 전에 안 사실이지만 A*알고리즘을 통해서도 풀 수 있다고 한다는데 정확한 방법은 차후 블로그 글로 소개해 드리겠습니다`