[SWEA] 1249. 보급로

문제

1249. [S/W 문제해결 응용] 4일차 - 보급로
출발지에서 도착지까지 가장 경로 중 복구시간이 가장 짧은 경로에 대한 총 복구 시간 구하기.

• 이동거리는 무시가능 (복구시간에 비해 매우 작은 소요시간)
• 파손깊이와 복구시간은 비례
• 이동 : 상하좌우 1칸씩

풀이

BFS 근데 이제 DP를 곁들인 풀이 (결과적으로 다익스트라?!)
map[][] : 지도 상태 저장
p[][] : 출발점에서부터 해당좌표까지의 최소 비용 저장

1. p의 모든 좌표를 MAX값으로 초기화한다.
2. 방문 시, 갱신되는 이동거리가 p값보다 작으면 -> 갱신하고, queue에 넣어서 다음번에 방문한다.

자바코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.io.FileInputStream;


class Solution
{
	static int N;
	static int [][] map = new int [100][100];
	static int [][] p = new int [100][100];
	
	static int [] dr = {-1, 0, 1, 0};
	static int [] dc = {0, -1, 0, 1};
	
	static final int MAX = 987654321;

	public static void main(String args[]) throws Exception
	{

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		String line;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			N = sc.nextInt();
			
			for (int i=0; i<N; i++) {
				line = sc.next();
				for (int j=0; j<N; j++) {
					map[i][j] = line.charAt(j)-'0';
					p[i][j] = MAX; //init
				}
			}
			p[0][0] = 0;

			BFS();
			
			System.out.printf("#%d %d\n", test_case, p[N-1][N-1]);
		}
	}
	
	public static void BFS() {
		Queue<Cord> q = new LinkedList<>();
		q.add(new Cord(0, 0));
		
		Cord cur;
		int nr, nc, price;
		while(!q.isEmpty()) {
			cur = q.poll();
			
			for (int d=0; d<4; d++) {
				nr = cur.r+dr[d];
				nc = cur.c+dc[d];
				if (nr<0||nr>=N||nc<0||nc>=N) continue;
				
				price = p[cur.r][cur.c] + map[nr][nc];
				if (p[nr][nc] > price) {
					p[nr][nc] = price;
					q.add(new Cord(nr, nc));
				}
			}
		}
	}

	static class Cord{
		int r;
		int c;
		Cord(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}