🔍 문제

📌 입력

📌 출력

💻 제출

🤔 생각

처음에는 주어진 N의 값이 200 이하 이기 때문에 floyd로 풀려고 접근 했었다.
floyd 알고리즘은 시간복잡도가 O(n^3)이기 때문에 정점의 개수 N이 작다면 시도 해볼만 하다고 생각했다.

하지만 이번문제에서는 상하좌우 로만 이동이 가능하다는 조건이 있었기에 단순히 3중 반복문을 통해서 전체 순회를 하는 floyd를 억지로 넣으려고 하는 순간 문제 난이도가 올라갈 것 이라는 생각이 들었다.

그렇다면 남은 최단거리 알고리즘은 다익스트라, 벨먼-포드 알고리즘 인데 벨먼-포드는 현재 학습하지 않은 상태였다.

선택지가 없기에 다익스트라로 풀기 시작했다.

cost를 작은 순으로 계산해야하기 때문에 우선순위 큐를 적용 했으며 기존의 데이터를 담고 있는 2차원 배열은 그대로 두고 임시 배열을 하나 생성 해서 거리계산을 통해 갱신 하기로 했다.

📝 제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static int[][] map;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] dx = {0, 0, 1, -1}; //동 서 남 북
    static int[] dy = {1, -1, 0, 0}; //동 서 남 북
    static final int INF = 987654321; //충분히 큰값

    static class Node {
        int x;
        int y;
        int cost;

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

    public static void main(String[] args) throws IOException {
        int roop = 1;
        while (true) {
            N = Integer.parseInt(br.readLine());

            if (N == 0) break; //입력값이 0이면 입력이 존재하지 않음

            map = new int[N][N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            bw.write("Problem " + roop + ": " + dijkstra() + "\n");

            roop++;
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static int dijkstra() {
    	//cost 에 따른 우선순위 데이터 출력
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(a.cost, b.cost)
        );
        

        //총 거리계산을 위한 임시 배열 생성 및 초기화
        int[][] move = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(move[i], INF);
        }
		
        //첫번째 시작 위치 입력
        pq.offer(new Node(0, 0, map[0][0]));
        move[0][0] = map[0][0];
        

        while (!pq.isEmpty()) {
            Node now = pq.poll();
			
            if (now.x == N - 1 && now.y == N - 1) {
            	//최종 목적지 도착
                return now.cost;
            }

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

                if (range(nx, ny)) {
                	//거리값 비교하여 갱신
                    if (move[nx][ny] > move[now.x][now.y] + map[nx][ny]){
                        move[nx][ny] = move[now.x][now.y] + map[nx][ny];
                        pq.offer(new Node(nx,ny,move[nx][ny]));
                    }
                }
            }
        }
		
        //최종 목적지 찾기 실패
        return -1;
    }
	
    //배열 범위 안에서 작동하는지 검증
    static boolean range(int nx, int ny) {
        return 0 <= nx && nx < N && 0 <= ny && ny < N;
    }

}