[BAEKJOON] 녹색 옷 입은 애가 젤다지?

---

SWEA의 '등산로 조정' 문제와 유사하다고 느껴졌다.

1. [0][0]칸에서 시작해 [N-1][N-1] 칸까지 최소 비용으로 도달할 수 있는 완전 탐색을 한다.

2. BFS를 사용했으며 우선순위큐로 현재 비용이 더 작은 것부터 탐색한다.

3. 현재 비용이 더 작은 것은 어떻게 알 수 있는가 ?

4. visit 방문 체크를 하지 않고, 초기 값을 Integer.MAX_VALUE 값으로 설정해주어 현재까지의 비용과 비교하며 더 작은 값으로 갱신한다.

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
		int N = Integer.parseInt(br.readLine());
		int tc=1;
		while(N!=0) {
			int[][] arr = new int[N][N];
			int[][] rupee = new int[N][N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			for(int i=0; i<N; i++) {
				Arrays.fill(rupee[i], Integer.MAX_VALUE);
			}
			PriorityQueue<Point> q = new PriorityQueue<>((a, b) -> Integer.compare(a.size, b.size));
			q.offer(new Point(0, 0, arr[0][0]));
			while(!q.isEmpty()) {
				Point now = q.poll();
				int x = now.x;
				int y = now.y;
				int size = now.size;
				for(int d=0; d<4; d++) {
					int nx = x + dir[d][0];
					int ny = y + dir[d][1];
					if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
					if(size+arr[nx][ny] < rupee[nx][ny]) {
						rupee[nx][ny] = size+arr[nx][ny];
						q.offer(new Point(nx, ny, size+arr[nx][ny]));
					}
				}
			}
			sb.append("Problem ").append(tc).append(": ").append(rupee[N-1][N-1]).append("\n");
			N = Integer.parseInt(br.readLine());
			tc++;
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	public static class Point {
		int x, y, size;
		public Point(int x, int y, int size) {
			super();
			this.x = x;
			this.y = y;
			this.size = size;
		}
	}
}

 

[출처]

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

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