[Java] 백준 4485번 : 녹색 옷 입은 애가 젤다지?

1. 문제

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

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

 

 

 

2. 풀이과정

 

BFS를 사용한 이유

처음엔, dfs로 풀고 시간 초과가 났다. 생각해보니 이 문제는 가다가 해당 노드에 더 작은 비용으로 갈 수 있는 경우, 굳이 더 갈 필요가 없어서 버리기 때문에 bfs가 유리하다. dfs를 사용할 경우, 초반에 전체 탐색을 하기 때문에 시간 초과가 나는 것 같다.

 

 

Priority Queue를 사용한 이유

bfs임에도 priority queue를 쓴 이유는, 이 문제의 경우 거리가 가까운 것과 cost는 별개의 문제이기 때문이다. 즉, 거리가 가깝다고 최고의 선택이 되지 않는다. 그리고 cost가 작은 것으로 먼저 탐색할수록 필요없는 경로는 빨리 거를 수 있어서 불필요한 연산을 줄일 수 있다.

 

 

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

public class Boj4485 {

	static int N, map[][], result[][];
	static PriorityQueue<int[]> pq;
	public static void bfs(int x, int y, int cost) {
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		pq.offer(new int[] {x, y, cost});
		while(!pq.isEmpty()) {
			int[] node = pq.poll();
			
			//이걸 queue에 추가한 후에, 더 작은 case가 있으니 pass해라
			if(result[node[0]][node[1]] < node[2]) continue;
			
			for(int i=0;i<4;i++) {
				int nx = node[0] + dx[i];
				int ny = node[1] + dy[i];
				if(0<=nx && nx<N && 0<=ny && ny<N && result[nx][ny]>node[2]+map[nx][ny]) {
					result[nx][ny] = node[2]+map[nx][ny];//지금까지 쌓인 cost의 합 + 이동할 노드(nx, ny)의 cost
					pq.offer(new int[] {nx, ny, result[nx][ny]});
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		StringBuilder sb = new StringBuilder();
		int t = 1;
		while(true) {
			N = Integer.parseInt(br.readLine());
			if(N==0)break;
			map = new int[N][N];//입력값
			result = new int[N][N];//해당 노드까지의 최소 cost 저장
			pq = new PriorityQueue<>((o1, o2)->(o1[2]-o2[2]));
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					result[i][j] = 999_999_999;//최대로 초기화
				}
			}
			result[0][0] = map[0][0];
			bfs(0, 0, map[0][0]);
			sb.append("Problem ").append(t++).append(": ").append(result[N-1][N-1]).append("\n");
		}
		System.out.println(sb.toString());
	}
}