BJ4485 녹색 옷 입은 애가 젤다지?

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

각 칸을 이동할 때마다 비용이 필요하고, 목적지로 가는 데에 최소 비용을 구하는 문제이다.

DP와 BFS로 각 칸마다 필요한 최소거리를 갱신해주는 방식과 BFS나 DFS를 활용해 연산해 주는 방식이 있다.

두가지 코드를 모두 작성해보고, 어떤 이점이 있는 지 알아볼 수 있는 문제였다.

먼저 첫번째 코드는 DFS를 활용해 연산한 방식이다.
코드는 짧고 작성하기 간단하지만, 매 한칸마다 계속 연산을 해야하기 때문에 훨씬 오랜 시간이 걸려 문제의 제한시간 내에 통과하지 못했다.

package day0401;

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

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

	static void func(int x, int y, boolean[][] b, int sum) {
		if (sum > min)
			return;
		if (sum < min && x == N - 1 && y == N - 1) {
			min = sum;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nX = x + dir[0][i];
			int nY = y + dir[1][i];
			if (nX < N && nX >= 0 && nY < N && nY >= 0 && !b[nX][nY]) {
				boolean[][] nb = new boolean[N][N];
				for (int j = 0; j < N; j++) {
					for (int k = 0; k < N; k++) {
						nb[j][k] = b[j][k];
					}
				}
				nb[nX][nY] = true;
				func(nX, nY, nb, sum + map[nX][nY]);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		int tc = 0;
		while (true) {
			tc++;
			N = Integer.parseInt(br.readLine());
			if (N == 0) {
				bw.append("\n");
				break;
			}
			map = 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());
				}
			}
			min = -map[0][N - 1];
			for (int i = 0; i < N; i++) {
				min += map[0][i];
				min += map[i][N - 1];
			}
			func(0, 0, new boolean[N][N], map[0][0]);
			bw.append("Problem " + tc + ": " + min + "\n");
		}
		bw.flush();
	}
}

두번째 코드는 DP를 활용해 연산의 수를 많이 줄여 쉽게 제한시간 내에 통과할 수 있었다.

package day0401;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class GreenisZeldaDP {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N, t;
	static int[][] map, dp;
	static int[][] dir = { { 0, 1, 0, -1 }, { 1, 0, -1, 0 } };


	static void BFS() {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] { 0, 0 });
		dp[0][0] = map[0][0];

		while (!queue.isEmpty()) {
			int[] xy = queue.poll();
			int x = xy[0]; 
			int y = xy[1]; 

			for (int d = 0; d < 4; d++) { 
				int nx = x + dir[0][d]; 
				int ny = y + dir[1][d];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N)
					continue;

				if ((dp[x][y] + map[nx][ny]) < dp[nx][ny]) {
					dp[nx][ny] = dp[x][y] + map[nx][ny];
					queue.offer(new int[] { nx, ny });
				}
			}
		}

	}

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