코드 복사/붙여넣기 하는 당신이 아름답습니다.

14442 : 벽 부수고 이동하기 2

풀이

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-22 17:54

Read more posts by this author