[다익스트라/자바] SWEA 4193. 수영대회 결승전

SW Expert Academy

문제 해석

1. 출발점부터 도착점까지 이동할 때 "최단 거리"를 구해야 함
2. 격자 공간 위에서 이동 조건이 존재
3. 이동할 때마다 가중치(이동 시간)는 기본 1
4. 하지만 소용돌이 구간은 가중치가 달라짐 (시간이 더 오래 걸림)
5. n은 2 이상 15 이하

위 조건을 고려했을 때, 모든 간선의 가중치가 양수이며 최단거리를 구하는 것이므로 다익스트라로 푸는 것을 먼저 고려해봤다. 다만, 아직 다익스트라가 익숙치 않은 탓에 우선순위 큐는 사용하지 않았고, 기본적인 BFS 로직 위에 최단 거리로 각 노드를 갱신하는 로직만 추가하여 구현하였다. 이렇게 할 경우에는 다익스트라의 시간복잡도가 O(V^2 + E) 정도이므로 시간 내에는 충분히 들어올 것으로 보았다.

(다익스트라가 아직 익숙치 않아서 우선순위큐를 사용하지 않고 BFS 로직 기반으로 구현하게 되었는데, 우선순위 큐를 사용하여 로직을 구성하면 조금 더 최적화가 가능할 것 같다.)

문제 풀이

package ssafy.사전학습;  

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Comparator;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  

public class 수영대회_결승전 {  

    public static int n;  
    public static int[][] arr;  
    public static int[][] ans;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int t = Integer.parseInt(st.nextToken());  
        for (int i = 1; i <= t; i++) {  
            st = new StringTokenizer(br.readLine());  
            n = Integer.parseInt(st.nextToken());  
            arr = new int[n][n];  
            ans = new int[n][n];  

            for (int j = 0; j < n; j++) {  
                st = new StringTokenizer(br.readLine());  
                for (int k = 0; k < n; k++) {  
                    arr[j][k] = Integer.parseInt(st.nextToken());  
                    ans[j][k] = Integer.MAX_VALUE;  
                }  
            }  
            st = new StringTokenizer(br.readLine());  
            int startY = Integer.parseInt(st.nextToken());  
            int startX = Integer.parseInt(st.nextToken());  
            st = new StringTokenizer(br.readLine());  
            int endY = Integer.parseInt(st.nextToken());  
            int endX = Integer.parseInt(st.nextToken());  

            bfs(new Node(startY, startX));  
            if (ans[endY][endX] == Integer.MAX_VALUE) {  
                System.out.println("#" + i + " " + -1);  
            } else {  
                System.out.println("#" + i + " " + ans[endY][endX]);  
            }  
        }  
    }  

    public static void bfs(Node start) {  
        int[] dx = new int[]{0, 1, 0, -1};  
        int[] dy = new int[]{1, 0, -1, 0};  
        Queue<Node> q = new LinkedList<>();  
        q.add(start);  
        ans[start.y][start.x] = 0;  

        while (!q.isEmpty()) {  
            Node now = q.poll();  
            int y = now.y;  
            int x = now.x;  

            for (int i = 0; i < 4; i++) {  
                int newY = y + dy[i];  
                int newX = x + dx[i];  
                if (canGo(newY, newX)) {  
                    if (arr[newY][newX] == 2) {  
                        int res = ans[y][x] + Math.abs((ans[y][x] % 3) - 2) + 1;  
                        if (res > ans[newY][newX]) {  
                            continue;  
                        }  
                        ans[newY][newX] = res;  
                    } else {  
                        int res = ans[y][x] + 1;  
                        if (res > ans[newY][newX]) {  
                            continue;  
                        }  
                        ans[newY][newX] = res;  
                    }  
                    q.add(new Node(newY, newX));  
                }  
            }  
        }  
    }  

    public static boolean inRange(int y, int x) {  
        return y >= 0 && y < n && x >= 0 && x < n;  
    }  

    public static boolean canGo(int y, int x) {  
        return inRange(y, x) && arr[y][x] != 1;  
    }  

    public static class Node {  
        int x, y;  

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

}