[BAE/<JOON> 문제풀이] 14442. 벽 부수고 이동하기 2

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

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

 

핵심::
기본 BFS 문제

풀이::
이 문제는 벽을 뚫고 이동할 수 있는 횟수가 1 이상이으므로 각 지점에서 벽을 뚫을 수 있는 횟수 별로

최단 거리를 따로 저장을 해줘야 한다.

의견::

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

struct node {
	int x, y, cnt, rk;
};


int mvx[4] = { 1, 0, -1, 0 };
int mvy[4] = { 0, 1, 0, -1 };

int main()
{
	int n, m, k; cin >> n >> m >> k;		
	if (n == 1 && m == 1) {
		cout << 1;
		return 0;
	}
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	vector<vector<vector<int>>> ch(n + 1, vector<vector<int>>(m + 1, vector<int>(11, 2100000000)));
	for (int i = 1; i <= n; i++) {
		string s; cin >> s;
		for (int j = 1; j <= m; j++) {
			arr[i][j] = s[j - 1] - 48;
		}
	}

	queue<node> q;
	q.push({ 1, 1, 1, 0 });
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int mx = cur.x + mvx[i];
			int my = cur.y + mvy[i];
			if (mx > n || mx < 1 || my > m || my < 1 ||
				cur.rk + arr[mx][my] > k) continue;
			if (ch[mx][my][cur.rk + arr[mx][my]] <= cur.cnt + 1) continue;
			ch[mx][my][cur.rk + arr[mx][my]] = cur.cnt + 1;
			if (mx == n && my == m) {
				cout << cur.cnt + 1 << "\n";
				return 0;
			}
			q.push({ mx, my, cur.cnt + 1, cur.rk + arr[mx][my] });
		}
	}

	cout << -1 << "\n";
	
	return 0;
}