백준 2178번. 미로 탐색 (Java)

Problem

• 문제 링크

N * M 크기의 미로가 주어졌을 때 (1, 1) 에서 (N, M) 위치로 가기 위한 최소 이동 칸 수를 구하는 문제입니다.

Solution

간단한 BFS 문제입니다.

Dot 클래스를 만들어서 (x, y) 좌표값과 현재까지 이동한 칸의 수 count 를 저장합니다.

BFS 를 돌면서 (N, M) 좌표에 도달했을 때 count 값을 출력하면 됩니다.

Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] maze = new int[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';
            }
        }

        int result = bfs(n, m, maze);
        System.out.println(result);
    }

    static int bfs(int n, int m, int[][] maze) {
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        Queue<Dot> q = new LinkedList<>();
        maze[0][0] = 0;
        q.add(new Dot(0, 0, 1));
        
        while (!q.isEmpty()) {
            Dot dot = q.poll();
            
            if (dot.x == n-1 && dot.y == m-1) {
                return dot.count;
            }

            for (int i=0; i<4; i++) {
                int nx = dot.x + dx[i];
                int ny = dot.y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (maze[nx][ny] == 1) {
                        maze[nx][ny] = 0;
                        q.add(new Dot(nx, ny, dot.count + 1));
                    }
                }
            }
        }

        return 0;
    }

    static class Dot {
        int x, y, count;

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