[BOJ]4485_녹색 옷 입은 애가 젤다지?(다익스트라)

뭔가 다익스트라가 BFS와 프림을 합쳐놓은 느낌이 들어서 계속 다익스트라만 골라 푸는 것 같다.

암튼 풀었으니 리뷰! 이제 골드문제도 딱히 두렵지 않다. 그냥 풀면 풀리는 것 같다(아직 다양한 유형을 안해봐서 그럴수도ㅋㅋ)

 

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

문제의 입력이 행렬로 주어졌다.

이전에 주로 연습했던 다익스트라는 간선정보(from, to, weight)로 주어진 것을 연습해서 행렬을 어떻게 다익스트로 풀지 살짝 막막했지만, 조금 고민해보면 접근은 같다.

 

행렬의 크기인 N이 최대125까지밖에 안된다. 고로 125*125크기의 int[] dist배열을 만들어도 된다는 것이다.

그럼 행렬[r][c]의 r,c를 일렬로 쭈욱 펼쳐서 dist에다가 1번부터 N*N까지 넣어줬다 생각을 하고 다익스트라를 쓰면 된다.

 

그리고 이 문제 역시 cost로 0이 들어올 수 있다. 따라서 visited로 이미 방문한 곳을 방문하지 못하게 막는 것은 예상과 다른 결과를 야기할 수 있다고 생각해서, 방문체크를 일절 하지 않았다. 방문체크는 어차피 속도를 높이기 위해 가지치기를 하는 것 뿐이라, 방문체크를 해야하는지 안해야하는지 애매하다면 그냥 체크를 안하는게 낫다고 판단했다.

 

암튼 해결방법의 키포인트는 64,65번 라인에 있는 dist[nr*N+nc+1]을 생각해내는 것 같다. 행렬 r,c좌표를 쫙 펼쳐서 dist에다가 넣는 것이다.

package 개인연습;

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

public class BOJ4485_녹색옷입은애가젤다지 {
	static class Point implements Comparable<Point>{
		int r;
		int c;
		int cost;
		public Point(int r, int c, int cost) {
			this.r = r;
			this.c = c;
			this.cost = cost;
		}
		@Override
		public int compareTo(Point o) {
			return this.cost - o.cost;
		}
	}
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = 0;
		while(true) {
			int N = Integer.parseInt(br.readLine());
			if(N == 0) break;
			int[][] mat = new int[N][N];
			for(int r=0; r<N; r++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int c=0; c<N; c++) {
					mat[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			
			int[] dist = new int[125*125+1];
			boolean[] visited = new boolean[125*125+1];
			int dest = N*N;
			Arrays.fill(dist, Integer.MAX_VALUE);
			dist[1] = mat[0][0];
			
			Queue<Point> pq = new PriorityQueue<Point>();
			pq.offer(new Point(0,0,mat[0][0]));
			while(!pq.isEmpty()) {
				Point point = pq.poll();
				int r = point.r;
				int c = point.c;
				
//				visited[r*N+c+1] = true;
//				if(r*N+c+1 == N*N) break;
				
				for(int i=0; i<4; i++) {
					int nr = r +dr[i];
					int nc = c +dc[i];
					
					if(nr>=0 && nr<N && nc>=0 && nc<N 
							&& dist[nr*N+nc+1] > dist[r*N+c+1]+mat[nr][nc]) {
						dist[nr*N+nc+1] = dist[r*N+c+1]+mat[nr][nc];
						pq.offer(new Point(nr,nc,mat[nr][nc]));
					}
				}
			}
			StringBuilder sb = new StringBuilder();
			sb.append("Problem ").append(++test).append(": ").append(dist[N*N]);
			System.out.println(sb);
		}
	}
}