/ BOJ

BOJ_4485_녹색옷입은애가젤다지?_JAVA

문제 : 녹색 옷 입은 애가 젤다지?

링크 : BOJ_4485_녹색 옷 입은 애가 젤다지?

접근 방식

다익스트라 알고리즘을 이용하여 최단거리를 구하면 되는 문제이다.

주어지는 값이 그래프의 인접행렬이나 간선으로 주어지지 않고 2차원 배열로 주어지기 때문에, 4방탐색을 통해 탐색하고 최단거리를 구할 수 있도록 한다.

소스 코드

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 BOJ_4485_녹색옷입은애가젤다지 {

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

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

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc=  0;
		while (true) {

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

			if (N == 0) {
				return;
			}

			int[][] arr = new int[N][N];
			StringTokenizer st;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			int answer = dijkstra(N, arr);
			System.out.printf("Problem " + (++tc) + ": " + answer+"\n");

		}

	}

	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);
		}

	}

}