[백준] 4485. 녹색 옷 입은 애가 젤다지? (Java)

[BOJ] 4485. 녹색 옷 입은 애가 젤다지?

📌 풀이 과정

다익스트라 알고리즘을 사용해 시작 지점에서 목표 지점까지의 최소 비용 경로를 찾아야 한다.

문제에서 비용은 각 위치의 루피 값으로 한다.

1. 우선순위 큐 사용
   방문해야 할 위치들을 관리하기 위해 우선순위 큐를 사용한다.
   큐에서 비용이 가장 작은 위치를 우선적으로 탐색해 효율성을 높인다.

2. 비용 갱신
   현재 위치에서 인접한 위치로 이동할 때, 그 위치까지의 최소 비용을 갱신한다.
   만약 새로운 경로 < 기존 경로 인 경우 해당 경로를 우선순위 큐에 추가 한다.

3. 방문 처리
   이미 방문한 위치는 다시 방문하지 않도록 체크하여 불필요한 계산을 방지한다.

✨ 제출 코드

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

	static int N;
	static int[][] map;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int test = 1;
		while(true) {
			N = Integer.parseInt(br.readLine());
			if(N == 0) break;
			
			map = new int[N][N];
			
			StringTokenizer st;
			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());
				}
			}
			
			
			System.out.println("Problem " + (test++) + ": " + dijkstra(0, 0, N-1, N-1));
			
		}
		
	}
	
	
	static int dijkstra(int sx, int sy, int ex, int ey) {
		
		boolean[][] visited = new boolean[N][N];
		int[][] minRupee = new int[N][N];
		for(int i = 0; i < N; i++) {
			Arrays.fill(minRupee[i], Integer.MAX_VALUE);
		}
		
		minRupee[sx][sy] = map[sx][sy]; // 시작 정점 비용 초기화
		
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		pq.offer(new int[] {sx, sy, minRupee[sx][sy]});
		
		while(!pq.isEmpty()) {
			int[] node = pq.poll();
			int x = node[0];
			int y = node[1];
			int cost = node[2];
			
			if(visited[x][y]) continue;
			visited[x][y] = true;
			
			if(x == ex && y == ey) return cost;
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;
				
				if(minRupee[nx][ny] > cost + map[nx][ny]) {
					minRupee[nx][ny] = cost + map[nx][ny];
					pq.offer(new int[] {nx, ny, minRupee[nx][ny]});
				}
			}
		}
		
		
		return -1;
	}

}

---

비슷한 유형 문제

[SWEA] 1249. 보급로