[알고리즘] Java / SWEA / 보급로 / 1249
[알고리즘] Java / SWEA / 보급로 / 1249
문제
접근 방식
다익스트라 알고리즘으로 (0,0) 위치에서 (N-1,N-1) 위치의 최단거리를 구한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Solution_1249_정현명 {
public static class Vertex implements Comparable<Vertex>{
int x;
int y;
int weight;
Vertex(int x, int y, int weight){
super();
this.x = x;
this.y = y;
this.weight = weight;
}
@Override
public int compareTo(Vertex o) {
return this.weight - o.weight;
}
}
static int N;
static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
static int[][] map;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int tc=1;tc<=T;tc++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i=0;i<N;i++) {
String line = br.readLine();
for(int j=0;j<N;j++) {
map[i][j] = line.charAt(j) - '0';
}
}
sb.append("#"+tc+" "+dijkstra()+"\n");
}
System.out.print(sb);
}
static int dijkstra() {
int distance[][] = new int[N][N];
for(int i=0;i<N;i++) {
Arrays.fill(distance[i], Integer.MAX_VALUE);
}
distance[0][0] = 0;
PriorityQueue<Vertex> pq = new PriorityQueue<>();
pq.offer(new Vertex(0, 0, 0));
while(!pq.isEmpty()) {
Vertex v = pq.poll();
for(int i=0;i<4;i++) {
int nextX = v.x + deltas[i][0];
int nextY = v.y + deltas[i][1];
if(nextX<0||nextX>=N||nextY<0||nextY>=N) continue;
if(distance[nextX][nextY] > distance[v.x][v.y]+ map[nextX][nextY]) {
distance[nextX][nextY] = distance[v.x][v.y]+ map[nextX][nextY];
pq.offer(new Vertex(nextX,nextY,distance[nextX][nextY]));
}
}
}
return distance[N-1][N-1];
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / SWEA / 보급로 / 1249), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-SWEA-보급로-1249저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)