문제 (BOJ 14442 기준)
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
풀이
1.
출발점에서 시작하여 상, 하, 좌, 우로 이동하면서 도착지점에 도달하는 문제이므로 BFS를 사용하여 문제를 해결한다.
2.
이 때 벽을 부수고 이동하는 새로운 조건이 추가되었으므로 벽에 대한 방문배열을 추가한다. (visit[x][y][brk] // brk개수만큼 벽을 부순 상태에서 x , y 좌표에 도달하였는지)
3.
BFS로 탐색을 하면서도 부순 벽의 개수의 조건 때문에 추가적인 검사가 필요하다.
a.
다음에 이동할 좌표가 0인가? (벽이 아닌 경우)
i.
벽이 아닌경우엔 그냥 지나가도 상관없다.
b.
다음에 이동할 좌표가 1인가? (벽인 경우)
i.
지금까지 부순 벽의 개수가 k개를 넘지 않는가?
•
BFS 함수
- start : 순회의 시작점
int bfs() {
queue<tuple<int, int, int, int>> q;
q.push({ 0,0,1,0 });
visit[0][0][0] = 1;
int find = -1;
int result = INF;
while (!q.empty()) {
auto [x, y, cnt, brk] = q.front(); q.pop();
if (x == N - 1 && y == M - 1) {
find = cnt;
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (graph[nx][ny] == 1 && brk < K && !visit[brk + 1][nx][ny]) {
visit[brk + 1][nx][ny] = 1;
q.push({ nx, ny, cnt + 1, brk + 1 });
}
else if (!visit[brk][nx][ny] && graph[nx][ny] == 0) {
visit[brk][nx][ny] = 1;
q.push({ nx, ny, cnt + 1, brk });
}
}
}
}
return find;
}
C++
복사
•
Main 함수 동작
int main() {
fastio;
string s;
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
cin >> s;
for (int j = 0; j < M; j++) {
graph[i][j] = (s[j] - '0');
}
}
cout << bfs();
return 0;
}
C++
복사
