/ SWEA

SWEA_1240_보급로_JAVA

문제 : 보급로

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_1249_보급로

접근 방식

출발지(0,0)에서 도착지(N-1,N-1) 까지 이동하는 경로 중, 땅을 복구하는 시간이 가장 짧은 경로를 찾아야 하는 문제이다.

2차원 배열이 주어진 상태에서, 시작점과 끝 점까지의 최단거리를 구하는 문제인데, 그 중에서 가중치에 마이너스가 존재하지 않는다.

여기까지 생각하면 다익스트라 알고리즘을 이용한 문제라는 것을 알아챌 것이다.

배열의 각 칸에는 가중치가 있고, 출발지에서 도착지까지의 가중치가 가장 작은 값을 구하여 출력하면 된다.

나는 앞서 설명한 대로 다익스트라 알고리즘을 이용하여 풀이했다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class SW_1249_보급로 {

	static int N, arr[][];

	static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for (int tc = 1; tc <= T; tc++) {

			N = Integer.parseInt(in.readLine());

			StringTokenizer st;
			arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				String str = in.readLine();
				for (int j = 0; j < N; j++) {
					arr[i][j] = str.charAt(j)-'0';
				}
			}
			System.out.printf("#%d %d\n",tc,dijkstra(N,arr));
		}

	}

	public static int dijkstra(int N, int[][] arr) {
		// 거리 배열 생성 : 정점 개수만큼
		int[][] distance = new int[N][N];

		// 방문 정보 저장
//		boolean[][] visited = new boolean[N][N];

		// 거리 배열 초기화
		for(int i=0;i<N;i++) {
			Arrays.fill(distance[i], Integer.MAX_VALUE);
		}
		distance[0][0] = arr[0][0];

		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(0, 0, arr[0][0]));

		while (!pq.isEmpty()) {
			Node temp = pq.poll();

			for (int d = 0; d < 4; d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];

				if(dx >= 0 && dx < N && dy >= 0 && dy < N &&
						distance[dx][dy] > distance[temp.x][temp.y] + arr[dx][dy]) {
					distance[dx][dy] = distance[temp.x][temp.y] + arr[dx][dy];
					pq.add(new Node(dx,dy,distance[dx][dy]));
				}

			}
		}

		return distance[N-1][N-1];
	}

	static class Node implements Comparable<Node> {
		int x;
		int y;
		int wei;

		public Node(int x, int y, int wei) {
			super();
			this.x = x;
			this.y = y;
			this.wei = wei;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.wei, o.wei);
		}

	}

}