[백준 2178번] 미로 탐색

문제 링크: 2178번 제목

https://www.acmicpc.net/problem/2178

 

최단거리를 찾으므로 BFS로 구현하는 것이 유리하며, 방문하는 새로운 칸에는 현재의 칸에 저장된 값보다 1만큼 큰 값을 저장한다.

코드에서는 이용하지 않았지만, maze 배열의 테두리를 0(이동할 수 없는 칸)으로 감싸게 되면 새로 이동할 칸이 maze를 벗어나지 않는지 체크할 필요가 없다.

 

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

public class Main {
​​​​static class Pos {
​​​​​​​​int row;
​​​​​​​​int col;
​​​​​​​​Pos(int row, int col) {
​​​​​​​​​​​​this.row = row;
​​​​​​​​​​​​this.col = col;
​​​​​​​​}
​​​​}
​​​​static int[][] maze;
​​​​static boolean[][] visit;
​​​​static int n;
​​​​static int m;

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​/* input */
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​int[] mn = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
​​​​​​​​n = mn[0];
​​​​​​​​m = mn[1];
​​​​​​​​maze = new int[n][m];
​​​​​​​​visit = new boolean[n][m];
​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​String s = br.readLine();
​​​​​​​​​​​​for (int j = 0; j < m; j++)
​​​​​​​​​​​​​​​​maze[i][j] = s.charAt(j) - '0';
​​​​​​​​}

​​​​​​​​/* logic */
​​​​​​​​int[] drow = {0, 0, 1, -1};
​​​​​​​​int[] dcol = {1, -1, 0, 0}; // 동서남북

​​​​​​​​Queue<Pos> queue = new LinkedList<>();
​​​​​​​​queue.offer(new Pos(0, 0));
​​​​​​​​visit[0][0] = true;

​​​​​​​​boolean dest = false;
​​​​​​​​int path = 0;
​​​​​​​​while (!queue.isEmpty()) {
​​​​​​​​​​​​Pos cur = queue.poll();
​​​​​​​​​​​​int row = cur.row;
​​​​​​​​​​​​int col = cur.col;

​​​​​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​​​​​int nrow = row + drow[d];
​​​​​​​​​​​​​​​​int ncol = col + dcol[d];
​​​​​​​​​​​​​​​​if (nrow<0||ncol<0||nrow>=n||ncol>=m||maze[nrow][ncol]==0)
​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​if (visit[nrow][ncol])
​​​​​​​​​​​​​​​​​​​​continue;

​​​​​​​​​​​​​​​​visit[nrow][ncol] = true;
​​​​​​​​​​​​​​​​maze[nrow][ncol] = maze[row][col]+1;
​​​​​​​​​​​​​​​​if (nrow==n-1 && ncol==m-1) {
​​​​​​​​​​​​​​​​​​​​dest = true;
​​​​​​​​​​​​​​​​​​​​break;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​queue.offer(new Pos(nrow, ncol));
​​​​​​​​​​​​}

​​​​​​​​​​​​if (dest)
​​​​​​​​​​​​​​​​break;
​​​​​​​​}
​​​​​​​​System.out.println(maze[n-1][m-1]);
​​​​}
}