백준 14442 : 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

 

벽 부수고 이동하기 1과 거의 유사한 문제다.

https://unfunhy.tistory.com/14?category=825141 

백준 2206 : 벽 부수고 이동하기

벽 부수고 이동하기 1은 하나의 벽만 부술 수 있는 반면 2는 문제에서 주어지는 k개까지 벽을 부수고 이동할 수 있다.

기본적인 로직은 1과 동일하다.

 

#include <iostream>
#include <queue>
#include <tuple>
#include <string>

using namespace std;

int n, m, k;
bool board[1000][1000];
int visited[1000][1000][11];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void bfs() {
	int curx, cury, curk, cur_dist, nx, ny, nk;
	queue<tuple<int,int, int>> q;
	q.emplace(0, 0, 0);
	visited[0][0][0] = 1;

	while (!q.empty()) {
		tie(curx, cury, curk) = q.front();
		q.pop();

		//bfs는 최단 거리 알고리즘으로 제일 처음 n, m에 도달했을 때가 최단거리임이 보장됨
		if (curx == m - 1 && cury == n - 1) break;

		for (int i = 0; i < 4; i++) {
			nx = curx + dx[i], ny = cury + dy[i];
			//바운더리를 벗어나는 경우
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			//벽을 만났는데 더이상 벽을 부수지 못하는 경우
            if (board[ny][nx] && curk >= k) continue;
			
			nk = curk + board[ny][nx];
            //이미 동일한 갯수만큼의 벽을 부수고 해당 위치를 방문한 경우
			if (visited[ny][nx][nk]) continue;

			q.emplace(nx, ny, nk);
			visited[ny][nx][nk] = visited[cury][curx][curk] + 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int ans = 0;
	string s;
	cin >> n >> m >> k;
	for (int y = 0; y < n; y++) {
		cin >> s;
		for (int x = 0; x < m; x++) {
			board[y][x] = s[x] - '0';
		}
	}
	bfs();
	for (int i = 0; i <= k; i++) {
		if (visited[n - 1][m - 1][i]) {
			ans = visited[n - 1][m - 1][i]; break;
		}
	}
	cout << (ans != 0 ? ans : -1);
	return 0;
}

메모리: 46100 kb

시간: 316 ms