[이코테] 미로 탈출 Java

이것이 코딩테스트다 - 미로탈출

P.152

 

아이디어

• 최단거리 같은 것을 구하는 것은 BFS 알고리즘으로 탐색해야된다. 이유는 바로 인접 노드부터 탐색하기 때문이다
• 미로의 좌표를 가는 곳마다 현재 노드 +1로 해주면 탈출구가 있는 (N,M) 에는 (1,1) 에서 출발 후 도달하는 거리가 나온다

코드

import java.util.*;

class tct4 {
    static class Node {
        int x,y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[][] graph;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int n,m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new int[n][m];
        // 1이 괴물있고 0이 괴물 없음
        sc.nextLine();
        for (int i=0; i<n; i++) {
            String tmp = sc.nextLine();
            for (int j=0; j<m; j++) {
                graph[i][j] = tmp.charAt(j) - '0';
            }
        }
        // 시작을 항상 (1,1)
        // 배열을 0번지 부터 사용해서 0,0으로 시작
        BFS(0,0);
        System.out.println(graph[n-1][m-1]);
    }

    public static void BFS(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x,y));
        while (!q.isEmpty()) {
            Node cv = q.poll();
            for (int i=0; i<4; i++) {
                int nx = cv.x + dx[i];
                int ny = cv.y + dy[i];
                // 범위가 유효하고
                if (nx>=0 && ny>=0 && nx<n && ny<m) {
                    if (graph[nx][ny] == 0) continue; // 0은 갈 수 없음
                    if (graph[nx][ny] == 1) {
                        graph[nx][ny] = graph[cv.x][cv.y] + 1;
                        q.offer(new Node(nx, ny));
                    }
                }
            }
        }
    }
}