문제 출처

1. 문제설명

  • NxM 행렬의 맵이 있다.
  • 0은 이동할 수 있는 곳, 1은 벽이 있는 곳이다.
  • (1,1)에서 (N,M)까지의 최단 경로를 구하려고 한다.
  • 만약 이동 중에 벽을 부수고 이동하는 게 더 효율적이라면 벽을 K개까지 부수고 이동한다.
    • 이동은 상하좌우로 한칸씩 이동할 수 있다.
  • 최단 경로를 구하라
    • 탈출할 수 없다면, -1 출력



2. 알고리즘 설계

  • BFS 문제이다.
  • 상하좌우로 한칸씩 이동하면서 가중치 값을 +1 해주면 된다.
  • 단, 벽을 부수고 이동했을 때와, 부수지 않고 이동했을 때 모두 확인



3. 로직

  • N*M 크기의 visited 배열을 사용하면, 목적지에 도착하면 바로 값을 리턴해버린다.
    • BFS 로직이 그렇기 때문에
  • 특정 지점을 벽을 부수고 이동했을 때와 부수지 않고 이동했을 때를 구분해야 한다.
    • N*M*K 크기의 visited 배열 사용



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1000;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
int n, m, k;
char arr[SZ][SZ];
bool visited[SZ][SZ][10];

typedef struct {
	int y, x, d, k;
}Pos;

int bfs() {
	queue<Pos> q;
	q.push({ 0,0,1,0 });
	visited[0][0][0] = true;

	while (!q.empty()) {
		Pos cur = q.front();
		q.pop();

		if (cur.y == n - 1 && cur.x == m - 1) return cur.d;

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.y + dy[dir];
			int nx = cur.x + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

			if (arr[ny][nx] == '0' && !visited[ny][nx][cur.k]) {
				q.push({ ny, nx, cur.d + 1, cur.k });
				visited[ny][nx][cur.k] = true;
			}
			if (arr[ny][nx] == '1' && cur.k < k && !visited[ny][nx][cur.k+1]) {
				q.push({ ny, nx, cur.d + 1, cur.k + 1 });
				visited[ny][nx][cur.k + 1] = true;
			}
		}
	}

	return -1;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	cout << bfs();
	return 0;
}