[BOJ] 4485 : Obstacle Course - travelbeeee

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

---

BFS DP

 DP[i][j] := (N -1, N -1) 에서 ( i, j ) 까지 가는 가장 작은 비용.

 (N-1, N-1) 에서 (0, 0) 까지 경로를 탐색해나가며 DP 배열을 채워나가면 문제를 해결할 수 있다. 현재 내 위치 (curX, curY) 에서 다음 위치 (nX, nY)로 이동할 때, dp[curX][curY] + map[nX][nY] 보다 이미 dp[nX][nY]가 작다면 해당 경로는 탐색해도 의미가 없으므로 탐색을 진행하지 않고, dp[nX][nY] 보다 값이 작을 때만 계속 BFS 탐색을 진행해나간다.

#include<iostream>
#include<queue>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int round = 1;
	while(true){
		int N, map[125][125] = {}, dp[125][125] = {}, dx[4] = { 0, -1, 0, 1 }, dy[4] = { -1, 0, 1, 0 };
		cin >> N;
		if (N == 0)
			break;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++){
				cin >> map[i][j];
				dp[i][j] = 99999999;
			}

		queue<pair<int, int>> q;
		q.push({ N - 1, N - 1 });
		dp[N - 1][N - 1] = map[N - 1][N - 1];

		while (!q.empty()) {
			pair<int, int> cur = q.front(); q.pop();
			for (int i = 0; i < 4	; i++) {
				int nX = cur.first + dx[i], nY = cur.second + dy[i];
				if (0 <= nX && nX < N && 0 <= nY && nY < N && dp[cur.first][cur.second] + map[nX][nY] < dp[nX][nY]) {
					dp[nX][nY] = dp[cur.first][cur.second] + map[nX][nY];
					q.push({ nX, nY });
				}
			}
		}
		cout << "Problem " << round << ": " << dp[0][0] << '\n';
		round++;
	}
	return 0;
}

---