백준 4485 녹색 옷 입은 애가 젤다지?

문제

---

4485번: 녹색 옷 입은 애가 젤다지? (acmicpc.net)

해결방법

---

• 2차원 배열로 입력받고 배열에서 위, 아래, 오른쪽, 왼쪽 인접한 곳과 간선이 있고 해당 간선의 가중치는 도착지의 도둑루피 값으로 설정하여 다익스트라 알고리즘을 진행하면 된다.

• 간선만 잘 설정해주면 무난한 다익스트라 문제가 되어 쉽게 풀린다.

• 처음에 틀려서 이유를 찾았는데 t 값을 증가를 시켜주지 않아서 출력할때 전부 Problem 1: result 로 출력 됬다… 항상 문제를 잘 살피자!!

동작과정

---

1. 2차원 배열을 입력받는다.

2. 시작지점을 0,0 으로 반복문을 시작한다.

3. 현재 위치에서 4방향을 확인하여 범위 안이고 방문하지 않은 곳이면 현재 위치의 value와 해당 위치의 도둑루피 값을 value로 설정하여 우선순위 큐에 추가한다.

4. 마지막 좌표에 도착했으면 해당 Edge의 value에 마지막 좌표까지의 모든 도둑루피 값이 저장되어 있으므로 그것을 출력해준다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
 * 	다익스트라를 통해 최단경로를 구한다.
 * 	4방향으로 인접한 곳과 Edge를 생성하고 해당 칸의 도둑루피를 거리로 둔다.
 */
public class Main {
	
	// 위치 정보
	private static class Point{
		int y;
		int x;
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	// 간선 정보
	private static class Edge{
		Point to;
		int value;
		public Edge(Point to, int value) {
			this.to = to;
			this.value = value;
		}
	}
	
	private final static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	private static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		// Problem 번호 t
		int t = 1;
		while(true) {
			
			// 맵의 크기 N, 0이 들어오면 종료
			N = Integer.parseInt(in.readLine());
			
			if(N == 0)
				break;
			
			int[][] map = new int[N][N];
			
			for(int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				for(int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int result = -1;
			
			// 간선들을 저장할 우선순위 큐
			PriorityQueue<Edge> edges = new PriorityQueue<>((o1, o2) -> o1.value - o2.value);
			
			// 방문 체크
			boolean[][] visited = new boolean[N][N];
			
			// 초기 값 설정
			edges.offer(new Edge(new Point(0, 0), map[0][0]));
			
			while(!edges.isEmpty()) {
				// 새롭게 도착한 위치
				Edge now = edges.poll();
				
				// 방문체크
				if(visited[now.to.y][now.to.x])
					continue;
				
				// 방문체크
				visited[now.to.y][now.to.x] = true;
				
				// 목적지 도착
				if(now.to.y == N-1 && now.to.x == N-1)
					result = now.value;
				
				// 다음 위치 설정
				for(int d = 0; d < 4; d++) {
					int dy = now.to.y + D[d][0];
					int dx = now.to.x + D[d][1];
					
					if(isInBound(dy, dx) && !visited[dy][dx]) {
						edges.offer(new Edge(new Point(dy, dx), now.value + map[dy][dx]));
					}
				}
			}
			
			// 출력 
			sb.append("Problem " + t + ": " + result + "\n");
			t++;
		}

		out.write(sb.toString());
		out.flush();
	}
	
	// 경계확인
	private static boolean isInBound(int y, int x) {
		return y >= 0 && y < N && x >= 0 && x < N;
	}
}