99클럽 코테 스터디 15일차 TIL [Dijkstra]

- 오늘의 학습 키워드 : Dijkstra

[문제 이름 : 미로만들기 (백준 2665, G4)]
문제 url : https://www.acmicpc.net/problem/2665

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static int n;
    static int[][] map;
    static int[][] dist;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static final int MAX = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dist = new int[n][n];

        for(int i=0; i<n; i++) {
            String input = br.readLine();
            for(int j=0; j<n; j++) {
                map[i][j] = input.charAt(j) - '0';
                // 초기 거리 무한대로 지정
                dist[i][j] = MAX;
            }
        }

        solution();
        System.out.println(dist[n-1][n-1]);
    }

    static void solution() {
        // 벽 부순 비용 적은 순으로 오름차순
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.add(new int[]{0,0,0}); // {x, y, 부순 벽 수}
        dist[0][0] = 0;

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0];
            int y = cur[1];
            int brokeWalls = cur[2];

            // 이미 최소값으로 갱신한 경우, 탐색 종료
            if(dist[x][y] < brokeWalls) continue;

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

                if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    int newBrokeWalls = brokeWalls + (map[nx][ny] == 0 ? 1 : 0);
                    if(newBrokeWalls < dist[nx][ny]) {
                        dist[nx][ny] = newBrokeWalls;
                        pq.add(new int[]{nx,ny,newBrokeWalls});
                    }
                }
            }
        }
    }
}

풀이 과정 (풀이 시간 : 30분)

1. map 배열에 미로 정보를 저장한다. 이때 0은 벽, 1은 빈 방을 의미한다.

2. dist 배열은 (x,y)까지 이동하는 데 필요한 최소 벽 부수기 횟수를 저장하며, 초기값은 MAX로 설정한다.

3. 우선순위 큐를 활용하여, 벽을 덜 부수고 이동한 경로를 우선적으로 탐색한다.

4. 네 방향으로 이동하면서, 벽을 부숴야 하는 경우 newBrokeWalls로 갱신한다. 이때, newBrokeWalls < dist[nx][ny]이면, 벽을 부쉈을 때 더욱 빠르게 이동할 수 있음을 의미하므로 dist 배열을 갱신해준다.
5. 도착 지점의 dist 배열 값을 리턴한다.

 

내일은 SDS 자회사인 회사의 자기소개서를 작성할 예정이다.