[백준] 2665. 미로만들기 (Java)

 

2665번: 미로만들기

 

태그는 다익스트라이지만 우선순위큐로도 풀 수 있다. (사실 우선순위큐로 풀었는데 질문글 보니 다익스트라 코드도 있어서 다익스트라로도 풀어봄...ㅎㅎ)

 

 

우선순위큐 풀이

• 좌표 정보 + 검은 방을 흰 방으로 바꾼 횟수를 class로 선언한 후 검은 방을 흰 방으로 바꾼 횟수가 작은 순으로 큐에서 뽑으면 된다.
• visited 배열로 방문 유무를 확인하며 다음 좌표가 검은방이면 cnt + 1, 흰 방이면 cnt값을 큐에 넣는다.
• 적은 횟수부터 탐색하기 때문에 끝방 좌표에 도착하자마자 바로 벽 부신 개수를 리턴해주면 된다. (다익스트라로 할 경우 바로 리턴하면 안됨)

 

코드

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

public class Main {
    static int N;
    static int[] px = new int[]{1, 0, -1, 0};
    static int[] py = new int[]{0, 1, 0, -1};
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] col = br.readLine().split("");

            for (int j = 0; j < N; j++)
                map[i][j] = Integer.parseInt(col[j]);
        }

        bw.write(String.valueOf(solve()));
        br.close();
        bw.close();
    }

    public static int solve() {
        PriorityQueue<Location> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cnt));
        pq.offer(new Location(0, 0, 0));
        visited[0][0] = true;

        while (!pq.isEmpty()) {
            Location loc = pq.poll();

            if (loc.x == N - 1 && loc.y == N - 1) return loc.cnt;

            for (int d = 0; d < 4; d++) {
                int nx = loc.x + px[d];
                int ny = loc.y + py[d];

                if (!isIn(nx, ny) || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                if (map[nx][ny] == 0)
                    pq.offer(new Location(nx, ny, loc.cnt + 1));
                else
                    pq.offer(new Location(nx, ny, loc.cnt));
            }
        }
        return 0;
    }

    public static boolean isIn(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }

    static class Location {
        int x;
        int y;
        int cnt;

        public Location(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

 

실행 결과

 

다익스트라 풀이

• 검은 방을 흰 방으로 바꾼 횟수를 저장할 int형 visited 배열이 필요하다.
• MAX값 (2500)으로 배열 초기화를 하고 (0, 0) = 0으로 바꿔준다.
• 우선순위큐에선 알아서 횟수가 작은 것부터 뽑아줬다면,
  다익스트라에선 하나씩 찾아보며 더 작은 값으로 갱신이 가능할 경우를 다 따져야 한다.
• 검은 방일 경우 현재 위치의 visited값 + 1,흰 방일 경우현재 위치의 visited값`으로 다음 좌표값을 갱신한다.
• 주의할 점은 끝방에 도달할 때 위에서 오는 횟수랑 왼쪽에서 오는 횟수가 다를 수 있으므로 큐를 다 돌고 나서 마지막에 끝방 좌표값을 출력해줘야 한다.

 

코드

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

public class Main {
    static int N;
    static int[] px = new int[]{1, 0, -1, 0};
    static int[] py = new int[]{0, 1, 0, -1};
    static int[][] map;
    static int[][] cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        cnt = new int[N][N];
        for (int[] col : cnt)
            Arrays.fill(col, 2500);
        cnt[0][0] = 0;

        for (int i = 0; i < N; i++) {
            String[] col = br.readLine().split("");

            for (int j = 0; j < N; j++)
                map[i][j] = Integer.parseInt(col[j]);
        }

        solve();

        bw.write(String.valueOf(cnt[N - 1][N - 1]));
        br.close();
        bw.close();
    }

    public static void solve() {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(0, 0));

        while (!q.isEmpty()) {
            Point loc = q.poll();

            if (loc.x == N - 1 && loc.y == N - 1) continue;

            for (int d = 0; d < 4; d++) {
                int nx = loc.x + px[d];
                int ny = loc.y + py[d];

                if (!isIn(nx, ny)) continue;
                if (map[nx][ny] == 0) {
                    if (cnt[loc.x][loc.y] + 1 >= cnt[nx][ny]) continue;
                    cnt[nx][ny] = cnt[loc.x][loc.y] + 1;
                    q.offer(new Point(nx, ny));
                }
                else {
                    if (cnt[loc.x][loc.y] >= cnt[nx][ny]) continue;
                    cnt[nx][ny] = cnt[loc.x][loc.y];
                    q.offer(new Point(nx, ny));
                }
            }
        }
    }

    public static boolean isIn(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}

 

실행 결과