다익스트라

개념

• 최단경로는 여러개의 최단경로로 이루어져 있다.
• A --> B로 가는 최단경로를 찾는 문제이다.

1. 2차원 배열에서 다익스트라를 사용하기

• 보급로(https://github.com/AlwaysRYU/Daily_CodingTEST/blob/master/2021.9%EC%9B%94/J47.%EB%B3%B4%EA%B8%89%EB%A1%9C.md)

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

import com.sun.corba.se.internal.Interceptors.PIORB;

public class SOL02_보급로 {
	static int N;
	static int map[][];
	static int cost[][];
	static boolean visit[][];
	static int[] dx = { 0,0,1,-1};
	static int[] dy = { 1,-1,0,0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int Test = Integer.parseInt(br.readLine());
		for (int test = 1; test <= Test; test++) {
			
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			visit = new boolean[N][N];
			// 다익스트라
			// 1. 코스트 2차원 배열 생성
			cost = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				String strr = br.readLine();
				for (int j = 0; j < N; j++) {
					int temp = strr.charAt(j) - '0';
					map[i][j] = temp;
					// 2. 코스트 배열안에 모두 맥스로 채워준다.
					cost[i][j] = Integer.MAX_VALUE;
				}
			}
			// 입력 다 받음
			// 3. 연산 시작
			search();
			
			// 4. 출력
			System.out.println("#" + test + " " + cost[N-1][N-1]);
			
			
		}
	
	}
	static void search() {
		// 초기화 먼저 해주기
		PriorityQueue<Edge> PQ = new PriorityQueue<>(
				(e1, e2) -> e1.cost - e2.cost
				);
		
		// 가. 시작지점
		cost[0][0] = map[0][0];
		visit[0][0] = true;
		PQ.offer(new Edge(0,0, cost[0][0]));
		
		// 나. 큐돌리기 연산시작
		while (! PQ.isEmpty() ) {
			// 다. 큐에서 간선꺼내기.
			// 제일 작은놈이 앞에 있다.
			Edge e = PQ.poll();
			
			// 라. 꺼낸 좌표 x y를 기준으로 탐색 시작한다.
			for (int i = 0; i < 4; i++) {
				int nx = e.x + dx[i];
				int ny = e.y + dy[i];
				if ( nx <0 || nx >= N || ny <0 || ny >= N || visit[nx][ny] ) continue;
				// 마. 방문하지않고, 범위 내라면
				// 마2. 현재 코스트 배열보다, 새로 계산한 비용이 적다면 방문한다.
				// 마3. 이것이 키포인트이다.
				if ( e.cost + map[nx][ny] < cost[nx][ny] ) {
					visit[nx][ny] = true;
					cost[nx][ny] = e.cost + map[nx][ny];
					PQ.offer(new Edge(nx,ny, cost[nx][ny]));
				}
			}
			
		}
		
	}
	static class Edge{
		int x;
		int y;
		int cost;
		
		public Edge(int x, int y, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.cost = cost;
		}
	}
}