[BOJ - JAVA] 백준 2178: 미로탐색

Problem

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

2178번: 미로 탐색

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

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

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

Input

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

 

Output

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

---

문제 해결 과정

1. 좌측 상단에서 우측 하단까지의 거리 중 최단거리를 구하는 것이므로 BFS 탐색 알고리즘을 먼저 떠올렸다.
    - BFS 알고리즘의 경우 한 부모 노드에 연결된 자식 노드들을 큐에 넣어서 탐색을 진행하기 때문에 최단 거리를 구하는 문제에 최적화 되어 있다. 
2. 또한 각 좌표의 정보와 좌측 상단 (0,0)부터 해당 좌표까지의 최단거리를 저장 할 Pair클래스를 생성한다.
3. (0, 0) 좌표부터 bfs 탐색 시작 
   - 이 때 시작 지점도 칸 수에 포함이 되므로 거리는 1부터 시작!
4. 탐색하는 좌표가 우측 하단 값 (N-1, M-1)에 도달했다면 값 출력 후 프로그램 종료

 

---

My Solution Code

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

public class Main {
    static class Pair {
        int x, y, dist;

        public Pair(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }

    static int N, M;
    static int[][] maze;
    static boolean[][] visited;

    // 사방 탐색
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        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 str = br.readLine();
            for(int j = 0; j <M; j++) {
                maze[i][j] = str.charAt(j);
            }
        }

        bfs(new Pair(0, 0, 1));
    }

    // 거리 탐색 bfs
    static void bfs(Pair p) {
        Pair[] pairs = new Pair[N*M];
        int front =-1;
        int rear = -1;

        pairs[++rear] = p;

        visited[p.x][p.y] = true;

        while(front != rear) {
            Pair tmp = pairs[++front];

            // (N, M)에 도착하면 종료
            if(tmp.x== N-1 && tmp.y == M-1) {
                System.out.println(tmp.dist);
                break;
            }

            // 사방 탐색 시작
            for(int k = 0; k<4; k++) {
                int nx = tmp.x + dx[k];
                int ny  = tmp.y + dy[k];

                // 범위 내에 있고 방문하지 않았으며 길이 있는 경우
                if(checkValidation(nx, ny) && !visited[nx][ny] && maze[nx][ny] == '1')  {
                    visited[nx][ny] = true;
                    pairs[++rear] = new Pair(nx, ny, tmp.dist+1);
                }
            }
        }

    }

    // 범위 체크
    static boolean checkValidation(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}