1.문제

2.코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static class Node implements Comparable<Node>{
		int y,x,leng;
		
		Node(int y, int x, int leng){
			this.y = y;
			this.x = x;
			this.leng = leng;
		}

		@Override
		public int compareTo(Node o) {
			return this.leng-o.leng;
		}
	}
	
	static int[][] cave,leng;
	static boolean[][] visited;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int count = 1;
        while(true) {
	    	int N = Integer.parseInt(br.readLine());
	    	if(N==0) {
	            bw.flush();
	            bw.close();
	            br.close();
	    		return;
	    	}
	    	//동굴,방문배열 생성
	    	cave = new int[N][N];
	    	visited = new boolean[N][N];
	    	leng = new int[N][N];
	    	
	    	for(int i=0; i<N; i++) {
	    		Arrays.fill(leng[i], Integer.MAX_VALUE);
	    	}
	    	//동굴 정보 입력
	    	for(int i=0; i<N; i++) {
	    		StringTokenizer st = new StringTokenizer(br.readLine());
	    		for(int j=0; j<N; j++) {
	    			cave[i][j] = Integer.parseInt(st.nextToken());
	    		}
	    	}
	    	
	    	PriorityQueue<Node> queue = new PriorityQueue<Node>();
	    	
	    	leng[0][0] = cave[0][0];
	    	queue.add(new Node(0,0,leng[0][0]));
	    	
	    	int[] move_y = {1,-1,0,0};
	    	int[] move_x = {0,0,-1,1};
	    	
	    	while(!queue.isEmpty()) {
	    		Node curr = queue.poll();
	    		
	    		if(visited[curr.y][curr.x]) continue;
	    		
	    		visited[curr.y][curr.x] = true;
	    		
	    		if(curr.y==N-1 && curr.x==N-1) {
	    			bw.write("Problem "+count+": "+curr.leng+"\n");
	    			count++;
	    			break;
	    		}
	    		
	    		for(int i=0; i<4; i++) {
	    			int new_y = curr.y+move_y[i];
	    			int new_x = curr.x+move_x[i];
	    			
	    			if(new_y<0 || new_y>=N || new_x<0 || new_x>=N || visited[new_y][new_x]) continue;
	    			
	    			queue.add(new Node(new_y,new_x,curr.leng+cave[new_y][new_x]));
	    		}
	    	}
        }

    }
}

3.Reveiw

도착지점까지 갔을때 잃는 루피의 최소거리를 구해줘야 하므로 다익스트라 알고리즘을 사용하였다.

우선순위큐를 사용하여 시간을 줄여주었고 우선순위큐에서 컴퍼레이블을 사용하여 루피의 누적 수를 기준으로 poll을 하게 변경해주었다.