풀이
dp[x][y][부순 벽의 수 k]로 두고 풀자.
BFS를 돌리면 된다.
하지만 중요한 건 문제 풀이가 아니고(!) memset이 byte 단위로 초기화하기 때문에
memset(dp, 1, sizeof(dp)) 하면 dp의 각 방이 0x01010101 이렇게 채워진다는 걸 배웠다.
그래서 987654321이나 1e9처럼 int_max 절반으로 초기화하고 싶으면 0x3f로 초기화하면 된다.
음… 어셈 공부하다 말았는데 계속 해야하나? ㅠㅠ
코드
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
const int dx[] = { 0,1,-1,0 };
const int dy[] = { 1,0,0,-1 };
int N, M, K;
int dp[1001][1001][11];
char A[1001][1001];
struct ABC {
int x, y, k;
ABC(int x, int y, int k) : x(x), y(y), k(k) {}
};
int main() {
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < N; ++i)
scanf("%s", A[i]);
queue<ABC> q;
q.push(ABC(0, 0, 0));
memset(dp, 0x3f, sizeof(dp));
dp[0][0][0] = 1;
while (!q.empty()) {
ABC now = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = now.x + dx[i], ny = now.y + dy[i];
int nk = now.k + A[nx][ny] - '0';
int nd = dp[now.x][now.y][now.k] + 1;
if (nx < 0 || N <= nx || ny < 0 || M <= ny) continue;
if (nk <= K && dp[nx][ny][nk] > nd) {
dp[nx][ny][nk] = nd;
q.push(ABC(nx, ny, nk));
}
}
}
int ans = 1e9;
for (int i = 0; i <= K; ++i) ans = min(ans, dp[N - 1][M - 1][i]);
if (ans == 1e9) ans = -1;
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이