문제 확인

그래프 이론 분류의 실버 1 난이도 문제이다.

문제를 읽고 "최소의 칸 수"를 구하는 프로그램이라는 단어를 보고,
전에 DFS/BFS 이론을 공부할 때 BFS가 최단거리를 구하는 문제에서 유리하다고 했던 것이 생각나서 바로 BFS 알고리즘을 생각하였다.

풀이

미로를 표시하기 위한 배열(maze), 방문했는지 표시하기 위한 배열(visited) 총 두개의 2차원 배열을 만든다.
maze를 (0,0)부터 반복문을 통해 돌면서 방문하는 곳을 visited에 표시해준다. 그리고 상하좌우 인접한 배열을 확인하여 이동할 수 있는 좌표이고(maze 배열에서 0으로 표시 되지 않은 곳), 방문하지 않은 좌표라면 queue에 해당 좌표를 넣고 maze의 해당 좌표 값을 이동하기 전 좌표 값 +1 해준다.

위 과정을 queue가 비워질 때까지 반복하면 된다. 그러면 maze[N-1][M-1]의 값에 거쳐온 최소 칸의 수가 들어가게 된다.

public class Main {

    static int N, M;
    static int[][] maze;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -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());

        maze = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();  //  String 문자열을 char형 배열로 바꿔준다.
            for (int j = 0; j < M; j++) {
                maze[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
            }
        }

        bfs(0, 0);
        System.out.println(maze[N - 1][M - 1]);
    }

    static void bfs(int x, int y) {
        Queue<point> q = new LinkedList<>();
        q.add(new point(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            point start = q.poll();
            for (int i = 0; i < 4; i++) {
                int newX = start.x + dx[i];
                int newY = start.y + dy[i];

                if (newX >= 0 && newX < N) {
                    if (newY >= 0 && newY < M) {
                        if (maze[newX][newY] != 0 && !visited[newX][newY]) {
                            maze[newX][newY] = maze[start.x][start.y] + 1;
                            q.add(new point(newX, newY));
                            visited[newX][newY] = true;
                        }
                    }
                }
            }
        }
    }

    static class point {
        int x;
        int y;

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

참고

1. 2차원 배열을 탐색하며 최단 거리를 구하는 것이기 때문에 dx, dy 테크닉을 사용해야한다.
   dx,dy 테크닉이란 그래프에서 방향 전환을 위해 미리 정의해둔 배열을 사용하는 것이다.

//	예시
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};

2. String.valueOf(charArray[j])
   parseInt는 인자로 문자열을 받아야하는데 charArr[j]는 문자(char)형이기 때문에 String의 메서드인 valueOf를 사용하여 문자열로 변환 후 parseInt의 인자로 넣어준다.