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

문제

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

풀이

• 도둑루피를 획득하면 소지한 루피가 감소
• (0, 0)에서 (n-1, n-1)로 이동
• 상하좌우로만 이동 가능
• 잃는 금액을 최소로 하여 이동한 결과 출력

간선의 가중치를 최소로 하여 이동하는 다익스트라 문제입니다.
저는 이를 BFS+메모이제이션을 활용하여 풀어봤습니다.

입력

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			n = Integer.parseInt(br.readLine());
			if (n == 0) break;
			
			map = new int[n][n];
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			dist = new int[n][n];
			for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF);

• n: 한 변의 길이
  • n == 0이면 종료
• map: 지도의 정보
• dist: 잃은 루피의 정보를 담을 배열
  • 메모이제이션을 사용할 것이기 때문에 모든 좌표의 값을 최댓값으로 초기화

탐색

	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { 0, 0 });
		dist[0][0] = map[0][0];
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			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) continue;
				
				int tmp = dist[r][c] + map[nr][nc];
				if (dist[nr][nc] > tmp) {
					dist[nr][nc] = tmp;
					queue.add(new int[] { nr, nc });
				}
			}
		}
	}

• 시작점(0, 0)부터 탐색 시작
• dist에 시작점 값 삽입
  • 시작점에서 잃는 값은 무조건 잃기 때문
• 4방 탐색
• 만약 탐색하려는 좌표의 값보다 (현재까지의 값 + 탐색하려는 좌표의 가중치)가 더 작을 경우 업데이트
  • 업데이트 했다면, 큐에 다음 좌표 삽입

출력

			bfs();
			sb.append("Problem ").append(++t).append(": ").append(dist[n-1][n-1]).append('\n');
		}
		
		System.out.println(sb.toString());

• 도착지 (dist[n-1][n-1])값 출력

코드

import java.util.*;
import java.io.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[][] map, dist;
	
	static int t = 0;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	static final int INF = 1_000_000_000;
	
	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { 0, 0 });
		dist[0][0] = map[0][0];
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			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) continue;
				
				int tmp = dist[r][c] + map[nr][nc];
				if (dist[nr][nc] > tmp) {
					dist[nr][nc] = tmp;
					queue.add(new int[] { nr, nc });
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			n = Integer.parseInt(br.readLine());
			if (n == 0) break;
			
			map = new int[n][n];
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			dist = new int[n][n];
			for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF);
			
			bfs();
			sb.append("Problem ").append(++t).append(": ").append(dist[n-1][n-1]).append('\n');
		}
		
		System.out.println(sb.toString());
	}
}