[알고리즘] 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
	static int max;
	static int sum;
	static boolean[][] visited;
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] map;
	static int[][] dp;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; testCase++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N+1][N+1];
			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("#").append(testCase).append(" ").append(dijkstra()).append("\n");
			
			// dp 시도
//			dp = new int[N+1][N+1];
//			for (int i = 0; i <= N; i++) {
//				Arrays.fill(dp[i], Integer.MAX_VALUE);
//			}
//			for (int i = 1; i <= N; i++) {
//				for (int j = 1; j <= N; j++) {
//					if (i == 1 && j == 1) {
//						dp[i][j] = map[i][j];
//						continue;
//					}
//					dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + map[i][j];
//				}
//			}
//			System.out.println(dp[N][N]);
			
			
//			max = Integer.MIN_VALUE;
//			visited = new boolean[N][N];
//			sum = 0;
//			visited[0][0] = true;
//			dfs(new Point(0, 0));
		}
		System.out.println(sb);
	}

	// dfs 시도
//	private static void dfs(Point point) {
//		if (point.equals(new Point(N-1, N-1))) {
//			max = Math.max(max, sum);
//		}
//		
//		for (int i = 0; i < 4; i++) {
//			int nx = point.x + dx[i];
//			int ny = point.y + dy[i];
//			
//			if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
//				visited[nx][ny] = true;
//				sum += map[nx][ny];
//				dfs(new Point(nx, ny));
//				sum -= map[nx][ny];
//				visited[nx][ny] = false;
//			}
//		}
//	}
	
	private static int dijkstra() {
		int[][] distance = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				distance[i][j] = Integer.MAX_VALUE;
			}
		}
		
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
		boolean[][] visited = new boolean[N][N];
		visited[0][0] = true;
		distance[0][0] = 0;
		pq.add(new int[] {0, 0, 0});
		
		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			if (cur[1] == N-1 && cur[2] == N - 1) {
				return cur[0];
			}
			
			for (int i = 0; i < 4; i++) {
				int dist = cur[0];
				int nx = cur[1] + dx[i];
				int ny = cur[2] + dy[i];
				
				if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
					if (distance[nx][ny] > dist + map[nx][ny]) {
						distance[nx][ny] = dist + map[nx][ny];
						visited[nx][ny] = true;
						pq.add(new int[] {distance[nx][ny], nx, ny});
					}
				}
			}
		}
		return 0;
		
	}
}

나의 풀이

- dfs로 하면 너무 느리고 dp로 하면 원하는 답이 안나온다.(사방 탐색이 가능하니)

- weight가 양수인 걸 이용해서 dijkstra를 한다.

- 다익스트라에서 Priority Queue를 안쓰면 O(V^2), 쓰면 O(ElogV)인데 O(VElogV)가 아닌 이유는 VE에서 E를 하나의 노드에 연결된 엣지라고 보았기 때문이다. 그런데 여기서 E는 모든 엣지의 총 개수이다. 즉, 사실상 E = VE인 것이다. 왼쪽 E와 오른쪽 E는 다르다! 양방향이라고 생각해보자. 오른쪽 E를 N이라고 하면 N * V가 된다. 즉, 양방향이기 때문에 이렇게 되는 것이다.