[JAVA] SWEA 보급로

문제 링크

SW Expert Academy

풀이 후기

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

거의 유사한 문제. 2차원을 그래프로 생각하여 시작점에서 도착점까지의 가장 적은 비용으로 가는 경로를 찾는 문제

import java.util.*;
import java.io.*;

public class Solution {
	
	public static class Node implements Comparable<Node>{
		int row, col, weight;
		public Node(int r, int c, int w) {
			row = r;
			col = c;
			weight = w;
		}
		public int compareTo(Node o) {
			return weight-o.weight;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int[][] d = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
		
		for(int t=1; t<=T; t++) {
			int N = Integer.parseInt(br.readLine());
			char[][] map = new char[N][N];
			int[][] dist = new int[N][N];
			boolean[][] visit = new boolean[N][N];
			
			for(int i=0;i<N;i++) {
				map[i] = br.readLine().toCharArray();
				Arrays.fill(dist[i],10000);
			}
			
			PriorityQueue<Node> pq = new PriorityQueue<>();
			dist[0][0] = map[0][0]-'0';
			pq.add(new Node(0, 0, dist[0][0]));
			
			while(!pq.isEmpty()) {
				Node cur = pq.poll();
				
				if(visit[cur.row][cur.col]) continue;
				visit[cur.row][cur.col] = true;
				
				if(cur.row==N-1 && cur.col==N-1) break;
				
				for(int i=0;i<4;i++) {
					int nr = cur.row + d[0][i];
					int nc = cur.col + d[1][i];
					
					if(0<=nr && nr<N && 0<=nc && nc<N) {
						int w = map[nr][nc]-'0';
						
						if(dist[nr][nc] > cur.weight+ w) {
							dist[nr][nc] = cur.weight+ w;
							pq.add(new Node(nr, nc, dist[nr][nc]));
						}
					}
				}
			}
			
			System.out.println("#"+t+" "+dist[N-1][N-1]);
		}
	}

}