[엘리스 알고리즘 코드 챌린지] Day 9. 격자 위의 ELICE (Java)

문제

제한 시간 : 7초

---

핵심

다익스트라 알고리즘을 사용하여 각 문자 위치 간의 최단 경로를 찾을 수 있다.

다익스트라 알고리즘의 시간 복잡도: O((V+E)logV), 여기서 V는 노드의 수, E는 간선의 수
전체 시간 복잡도: O(N^2 log N^2)

N이 1000일 때, 대략 1000^2 * log(1000^2) ≈ 10^8 정도의 연산이 필요하므로 7초 내에 충분히 해결 가능

 

전체 경로는 (1,1) -> E -> L -> I -> C -> E 순서로 이동하는 최단 경로의 합이 된다.

단 E는 두 개이므로 둘 중 어느 것을 먼저 방문했을 때, 더 빠른지 고려해야 한다.

---

Code (Java)

import java.util.*;

class Main {
    static int N;
    static int[][] grid;
    static int[][] dist;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] chars = new int[5][2];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        grid = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        for (int i = 0; i < 5; i++) {
            chars[i][0] = scanner.nextInt() - 1;
            chars[i][1] = scanner.nextInt() - 1;
        }
        
        int minTotalDist = Integer.MAX_VALUE;
        
        // 첫 번째 E와 두 번째 E에 대해 각각 계산
        for (int firstE = 0; firstE <= 4; firstE += 4) {
            int secondE = 4 - firstE;
            
            int startToE = dijkstra(0, 0, chars[firstE][0], chars[firstE][1]);
            int EtoL = dijkstra(chars[firstE][0], chars[firstE][1], chars[1][0], chars[1][1]);
            int LtoI = dijkstra(chars[1][0], chars[1][1], chars[2][0], chars[2][1]);
            int ItoC = dijkstra(chars[2][0], chars[2][1], chars[3][0], chars[3][1]);
            int CtoE = dijkstra(chars[3][0], chars[3][1], chars[secondE][0], chars[secondE][1]);
            
            if (startToE != -1 && EtoL != -1 && LtoI != -1 && ItoC != -1 && CtoE != -1) {
                int totalDist = startToE + EtoL + LtoI + ItoC + CtoE;
                minTotalDist = Math.min(minTotalDist, totalDist);
            }
        }
        
        System.out.println(minTotalDist == Integer.MAX_VALUE ? -1 : minTotalDist);
    }
    
    static int dijkstra(int sr, int sc, int er, int ec) {
        dist = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{sr, sc, 0});
        dist[sr][sc] = 0;
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int r = cur[0], c = cur[1];
            
            if (visited[r][c]) continue;
            visited[r][c] = true;
            
            if (r == er && c == ec) return dist[r][c];
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                
                int newDist = dist[r][c] + grid[r][c] + grid[nr][nc];
                if (newDist < dist[nr][nc]) {
                    dist[nr][nc] = newDist;
                    pq.offer(new int[]{nr, nc, newDist});
                }
            }
        }
        
        return -1; // 도달할 수 없는 경우
    }
}