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

흰색칸만 이동할 수 있는 미로에서 (0, 0)에서 (n-1, n-1)로 이동할 때 검정 칸으로 길이 막혀있다면, 검정칸을 최소로 변환시켜서 길을 뚫어주는 문제이다.

다익스트라라고 문제 유형이 있었는데 다익스트라는 보통 간선과 비용이 있는 인접리스트에서만 사용해봐서 이렇게 배열에서 그리고 비용 선정이 애매한 상황에서 어떻게 접근하면 좋을 지 몰라서 헤맸다.

Python

from heapq import heappush, heappop

n = int(input())

room = list(list(map(int, list(input()))) for _ in range(n))
cost = list([n*n] * n for _ in range(n))
cost[0][0] = 0

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

que = [(0, 0, 0)]

while que:
    count, y, x = heappop(que)

    if cost[y][x] < count:
        continue

    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]

        if 0 <= ny < n and 0 <= nx < n:
            if cost[ny][nx] > count + abs(room[ny][nx] - 1):    
                cost[ny][nx] = count + abs(room[ny][nx]-1)
                heappush(que, (cost[ny][nx], ny, nx))
print(cost[-1][-1])

먼저 방을 정의하고, 다익스트라를 위한 cost 리스트를 만들었다. 초기화는 최대값인 n*n을 넣어주었다.

que에는 바꾼 검정방의 수와 최초 시작점을 넣어주었고, 다익스트라를 시작했다.

비용이 가장 작은 칸을 꺼내기 위해 heap을 사용했다.
만약 현재 뽑은 칸에 저장된 count가 cost[y][x]보다 크다면 탐색을 생략했고, 그렇지 않다면 상하좌우 칸을 탐색하면서 count를 업데이트했다.

상하좌우 탐색하면서 경계를 벗어나는지 먼저 확인했고, count + abs(room[ny][nx] - 1)보다 cost[ny][nx]가 크다면 값을 업데이트했다.

abs(room[ny][nx]-1)을 한 이유는 흰 색 방은 1로 표현되고 검정방은 0이라서 검정방일 경우 뚫었다는 의미로 1을 더해주기 위함이다.

그래서 만약 cost[ny][nx]가 업데이트된 칸에 한해서 heap에 추가해주었다.

여기서 연산을 단순히 생각하고

cost[ny][nx] = min(cost[ny][nx], count + abs(room[ny][nx] - 1))
heappush((cost[ny][nx], ny, nx))

이렇게 if문을 통합시켜서 처리해버린 적이 있는데 이러면 cost가 업데이트가 되지 않아도 heap에 칸이 추가되어서 무한루프에 빠지게 된다.
다익스트라 할 때는 if문이 보기 싫더라도 왜 필요한지 조건을 잘 생각하면서 접근해야겠다.

Java

import java.util.*;

class Cell implements Comparable<Cell>{
    int cost, y, x;

    public Cell(int cost, int y, int x){
        this.cost = cost;
        this.y = y;
        this.x = x;
    }

    @Override
    public int compareTo(Cell other){
        return Integer.compare(this.cost, other.cost);
    }
}

public class Main { 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String line = scanner.nextLine();

        int n = Integer.parseInt(line);

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};

        int[][] room = new int[n][n];
        int[][] cost = new int[n][n];


        for (int i=0;i<n;i++){
            line = scanner.nextLine().strip();
            for(int j = 0;j<n;j++){
                room[i][j] = line.charAt(j) - '0';
                cost[i][j] = n*n;
            }
        }

        scanner.close();

        cost[0][0] = 0;

        PriorityQueue<Cell>  queue = new PriorityQueue<>();

        queue.add(new Cell(0, 0, 0));

        while(!queue.isEmpty()){
            Cell current = queue.poll();
            int count = current.cost;
            int y = current.y;
            int x = current.x;

            if(cost[y][x] < count){
                continue;
            }

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

                if(0 <= ny && ny < n && 0 <= nx && nx < n){
                    if(cost[ny][nx] > count + Math.abs(room[ny][nx] - 1) ){
                        cost[ny][nx] = count + Math.abs(room[ny][nx] - 1);
                        queue.add(new Cell(cost[ny][nx], ny, nx));
                    }
                }
            }
        }

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

자바에서는 PriorityQueue가 Heap의 역할을 대신 해준다. 그런데 python과 다르게 얘는 클래스로 입력받아야돼서 Cell이라는 클래스를 생성해주고, Comparable을 구현하고 메소드도 오버라이딩 해주어야한다.

기타 로직은 파이썬과 비슷하나 힙을 사용하기 위해서 특히 단순 숫자가 아닌 여러 항목이 있는 객체를 힙으로 비교해주려면 클래스를 새로 생성해줘야하는 것을 알게됐다.