[Java] 백준 2665번 : 미로만들기*

1. 문제

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

2665번: 미로만들기

 

 

2. 풀이 과정

1. 시작점에서 출발해서 bfs로 탐색한다.

2. PriorityQueue를 사용해서 변환 횟수가 적은 것부터 탐색하면, 해당 블럭마다 변환횟수가 가장 적은 경로로 탐색하게 되므로 도착점에 오는 순간 바로 종료한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static int N, result;
    static boolean visited[][];
    static char map[][];

    public static class Room implements Comparable<Room> {
        int x, y, v;

        public Room(int x, int y, int v){
            this.x = x;
            this.y = y;
            this.v = v;
        }

        @Override
        public int compareTo(Room o) {
            return this.v - o.v;
        }
    }

    public static void simulation(){
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        PriorityQueue<Room> pq = new PriorityQueue<>();
        pq.add(new Room(0, 0, 0));

        while(!pq.isEmpty()){
            Room room = pq.poll();
            if(room.x == N-1 && room.y == N-1){
                result = room.v;
            }

            for(int i=0; i<4; i++){
                int nx = room.x + dx[i];
                int ny = room.y + dy[i];
                if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]){continue;}
                visited[nx][ny] = true;
                int v = (map[nx][ny]=='0') ? room.v+1 : room.v;
                pq.add(new Room(nx, ny, v));
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N; i++){
            String s = br.readLine();
            for(int j=0; j<N; j++){
                map[i][j] = s.charAt(j);
            }
        }
        simulation();
        System.out.println(result);
    }
}

 

결과