[bfs] 벽 부수고 이동하기 2 14442

문제 해설 및 주의사항

 

 

---

 

풀이

1. 이전 문제에서 조건이 하나만 달라졌다.

- 벽을 1번만 부실수 있다 -> 벽을 k번 부실 수 있다.

---

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <tuple>
using namespace std;
// 벽 부수고 이동하기 2206
 
const int MAX = 1000;
 
// 칸 저장
int board[MAX][MAX];
// dist[i][j][k] : 좌표 (i, j) 를 0번 부수어 도착하거나 1번 부수어 도착하거나
int dist[MAX][MAX][11];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
 
int main(){
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%1d", &board[i][j]);
		}
	}
	
	queue<tuple<int, int, int>> q;
	// bfs 시작 처리
	dist[0][0][0] = 1;
	q.push(make_tuple(0, 0, 0));
	
	while(!q.empty()){
		int x, y, z;
		tie(x, y, z) = q.front(); q.pop();
		for(int coord = 0; coord < 4; coord++){
			int nx = x + dx[coord];
			int ny = y + dy[coord];
			
			// 범위 체크
			if(nx >= 0 && nx < n && ny >= 0 && ny < m ){
				// 다음 칸이 빈칸이고, 다음 칸에 방문한 적이 없을 때
				if(board[nx][ny] == 0 && dist[nx][ny][z] == 0){
					dist[nx][ny][z] = dist[x][y][z] + 1;
					q.push(make_tuple(nx, ny, z));
				}
				
				// 다음 칸이 벽이고, 아직 벽 k 번 부수지 않았고, 벽을 부수어 다음 칸에 방문한 적이 없을 때
				if(board[nx][ny] == 1 && z < k && dist[nx][ny][z + 1] == 0){
					dist[nx][ny][z + 1] = dist[x][y][z] + 1;
					q.push(make_tuple(nx, ny, z + 1));
				}
			}
		}
	}
	int ans = 123456789;
	for(int a : dist[n-1][m-1]){
		if(a != 0 && ans > a){
			ans = a;
		}
	}
	if(ans != 123456789){
		cout << ans << endl;
	}
	else{
		cout << -1 << endl;
	}
}

 

---

퇴고