swea 1249. [S/W 문제해결 응용] 4일차 - 보급로 Java (다익스트라)

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

문제에 저런 멘트가 있어서 혹시나 문제가 될까봐 문제 내용은 긁어오지 않았습니다.

아마 복제하여 문제로 출제하는 것을 문제삼는 것 같고 이런 풀이 글에는 상관없을 것 같긴 한데 혹시나..!

문제도 올려도 되는지 아시는 분 있으면 댓글 달아주세요!

풀이

다익스트라 기본 문제이다.

다익스트라는 가중치가 다른 그래프에서 최단 경로를 찾는 알고리즘으로, bfs + dp라고 볼 수 있다.

풀이 과정은 다음과 같다.

 

dp[r][c] = r,c좌표까지 오는 데 걸린 가중치
graph[r][c] = r,c좌표 한 칸의 가중치

 

1. 그래프의 크기만큼 2차원 배열 dp[][]를 만들고 INF를 넣어놓느다.(시작 지점은 제외)

2. 시작 노드에서 가중치(문제에선 깊이(=시간))를 0으로 두고 다익스트라로 탐색을 시작한다.(pq에 add)

3.1 현재 노드에 인접한 노드중, 갈 수 있는 노드(다음 노드)를 pq에 집어넣는다.

3.2 이때 pq는 가중치에 대한 최소 힙이어야 한다.(내부적으로 가중치 오름차순 자동 정렬)

4.1 dp[][]에 다음 노드의 가중치의 누적 합을 넣는다.

4.2 이때 다음 노드의 가중치의 누적 합이 dp[nr][nc]에 들어있던 가중치보다 크다면 스킵한다.

//최단 경로를 찾아야 하므로 이미 작은 값이 들어있다면 더 이상 탐색할 가치가 없다.

 

5.1 인접한 노드를 모두 탐색하고 다시 pq에 있는 노드를 꺼내서 탐색을 시작한다.

5.2 이때 꺼낸 노드의 가중치와 dp[꺼낸 노드.r][꺼낸 노드c]의 값을 비교하여 dp에 들어있는 값이 더 작다면 이 또한
     스킵한다.

//pq는 현재 가중치 기준 오름차순으로 정렬해놨기 때문에, pop하면 가중치가 가장 작은 노드가 튀어나온다.

 

6. 위의 과정을 도착 지점에 도달할 때까지 반복한다.

7. dp[도착지점.r][도착지점.c]이 답이다.

 

이해가 되지 않는 부분은 코드를 같이 보고, 우선적으로 다익스트라가 뭔지 찾아보길 바란다.

 

요즘 싸피에서 Java로 알고리즘 문제를 풀고 있다.

이제야 c++, Kotlin 왔다갔다 하는 데에 조금 적응했는데, 3언어는 좀 그렇다.

또 맥북이랑 윈도우 왔다갔다 하느라 키보드 적응 + 3언어 적응 중이라 효율은 떨어지지만

Java 다시 공부하는 셈치고 하고 있다.

자바에서 정렬 커스텀하는 것도 깃헙에 적어놔야지.

코드

import java.util.PriorityQueue;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Node implements Comparable<Node>{
	public int time;
	public int r;
	public int c;
	Node(int time, int r, int c){
		this.time = time;
		this.r = r;
		this.c = c;
	}
	@Override
	public int compareTo(Node node) {
		if(this.time < node.time) {
			return -1;
		}
		else if(this.time > node.time) {
			return 1;
		}
		return 0;
	}
}

//다익스트라
class Solution {

	static int n;
	static String[] graph = new String[100];
	static int[][] dp = new int[100][100];	
	static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
	
    static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue();
		pq.add(new Node(0,0,0));
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			//pq에 담겨있던 노드 탐색하려는데 이미 dp에 더 작은 값이 들어온 경우 스킵
			if(cur.time > dp[cur.r][cur.c]) continue;
			
			for(int i=0; i< 4; i++) {
				int nr = cur.r+dir[i][0];
				int nc = cur.c+dir[i][1];
				if(nr <0 || nr >=n || nc<0 || nc>=n) continue;
				//nr nc의 값이 현재 값보다 큰 경우만 탐색(갱신)
				int nextTime = cur.time + (int)(graph[nr].charAt(nc)-'0');
				if(dp[nr][nc]>nextTime) {
					dp[nr][nc] = nextTime;
					pq.add(new Node(nextTime,nr,nc));
				}
			}
		}
	}
	
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			// input
			n =Integer.parseInt(br.readLine());
			
			for(int i=0; i<n; i++) {
				graph[i] = br.readLine();
			}
			//dp maxvalue로 초기화
			for(int i=0; i<n ;i++) {
				for(int j=0; j<n; j++) {
					dp[i][j] = Integer.MAX_VALUE;
				}
			}
			dp[0][0] = 0;
			
			//solve
			dijkstra();
			//output
			System.out.println("#" + t+" " + dp[n-1][n-1]);
			
		}
	}
}