[백준/boj] 4485: 녹색 옷 입은 애가 젤다지? (Java) / BFS

문제

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

설명

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int[][] map, rupeeMap;
	static int N;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, -1, 0, 1 };

	static private class Pos {
		int x;
		int y;

		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		int t = 1;
		while (true) {
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;
			map = new int[N][N];
			rupeeMap = new int[N][N];
			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());
					rupeeMap[i][j] = Integer.MAX_VALUE;
				}
			}
			rupeeMap[0][0] = map[0][0];
			bfs();
			bw.append("Problem " + t + ": " + rupeeMap[N - 1][N - 1] + "\n");
			t++;
		}
		bw.flush();
		bw.close();
	}

	private static void bfs() {
		Deque<Pos> queue = new ArrayDeque<>();
		queue.add(new Pos(0, 0));
		while (!queue.isEmpty()) {
			int nx, ny;
			Pos pos = queue.poll();
			int x = pos.x;
			int y = pos.y;
			for (int i = 0; i < 4; i++) {
				nx = x + dx[i];
				ny = y + dy[i];
				if (!isRange(nx, ny))
					continue;
				if (rupeeMap[nx][ny] <= rupeeMap[x][y] + map[nx][ny])
					continue;
				rupeeMap[nx][ny] = rupeeMap[x][y] + map[nx][ny];
				queue.add(new Pos(nx, ny));
			}
		}
	}

	private static boolean isRange(int x, int y) {
		return x < 0 || y < 0 || x >= N || y >= N ? false : true;
	}

}

 

최단경로를 찾는 문제이다. 최단 경로 문제는 BFS가 더 좋은 접근 방법이다. (DFS로 풀면 시간 초과 난다..ㅎㅎ)

BFS 함수 내에서 좌표 값들을 최단 경로로 갱신해 주는데, 최단 경로가 아닌 경우에는 queue에 담기지 않도록 가지치기하는 것이 중요하다.

아래 코드에 해당한다.

if (rupeeMap[nx][ny] <= rupeeMap[x][y] + map[nx][ny])
	continue;

시뮬레이션

입력이 아래와 같은 경우

3
5 5 4
3 9 1
3 2 7
0

0. bfs 함수 진입 직후

rupeeMap

1. (0,0) 5 기준으로 이동 한 후 rupeeMap

여기서, '이동한 후'는 '사방탐색(while 문 안에 for문)하며 유효한 좌표를 모두 queue에 add한 후'를 의미한다.

주황색 네모박스로 표시된 좌표는 이동한 후 변화가 생긴 좌표다.

2. (0,1) 8 기준으로 이동 한 후 rupeeMap

사방탐색할 때, (0,0) 을 살펴보긴 하지만 rupeeMap[nx][ny] <= rupeeMap[x][y] + map[nx][ny] 에서 true를 반환하기 때문에 continue된다. (=> (0,0)은 queue에 다시 담기지 않는다.)

3. (1,0) 10 기준으로 이동 한 후 rupeeMap

(1,0) 기준으로 (1,1)로 이동했을 때, 잃는 루피(10+ map[1][0] = 19)가 더 많아진다. 이 경우엔 queue에 그 위치를 add 하지 않고 continue 하기 때문에 값이 바뀌지 않는다.

4. (2,0) 11 기준으로 이동 한 후 rupeeMap

5. (1,1) 17 기준으로 이동 한 후 rupeeMap

6. (0,2) 14 기준으로 이동 한 후 rupeeMap

rupeeMap[nx][ny] <= rupeeMap[x][y] + map[nx][ny]에서 18 <= 14 + 1 이 성립되지 않으므로 false가 반환된다.
18 -> 15 로 변경되고, (1,2) 15는 queue에 add 된다.

7. (2,1) 13 기준으로 이동 한 후 rupeeMap

8. (1,2) 15 기준으로 이동한 후 rupeeMap

변화 없음

9. (2,2) 20 기준으로 이동한 후 rupeeMap

변화 없음

이는 rupeeMap의 최종 모습이다. 따라서 답은 20이 된다.