(1,1)에서 시작하여 마지막 좌표 (N, M)로 향하는 최단거리 구하는 문제이며 BFS를 활용하는 전형적인 BFS문제이다.
하지만 벽을 부술 수 있는 기회를 딱 한 번 줌으로써 완전히 어려운 문제가 되었다.
실패한 아이디어
내가 생각한 아이디어는 우선 BFS를 돌리고, 기존 조건을 모두 통과한 뒤,
큐가 비면서도(갈 곳이 없는 상황) 벽 부술 수 있는 기회가 있는 조건을 만족하는 상황에서 BFS를 돌려 벽(1)이 없는 좌표만 큐에 추가해주었다.
(기껏 벽을 부수었는데 또 다시 벽을 만나면 벽을 부술 수 있는 기회가 의미가 없어지니 이렇게 설계했다..)
하지만 결과적으로 부술 수 있는 기회가 있어도 0이 있으면 0으로만 갔기 때문에, 중간에 벽을 부숨으로써 탈출할 수 있음에도 불구하고 탈출하지 못하는 반례가 생겼다.
/*
- 아이디어
- string으로 받음, 행, 열 순으로 입력
- (1,1)부터 시작, 시작거리부터 1로 시작해야 함
- 벽 한 개까지 부술 수 있음, 최단거리 구하기
- 탈출 못하면 -1 반환
*/
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define ll long long
string board[1002];
int dist[1002][1002];
int N, M;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++) {
cin >> board[i];
}
queue<pair<int, int>> Q;
dist[0][0] = 1;
Q.push({0,0});
int one_shot = 1;
while(!Q.empty()) {
auto cur = Q.front(); Q.pop();
for(int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if(dist[nx][ny] > 0 || board[nx][ny] == 1) continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx, ny});
}
// 모든 조건 통과했는데 갈 곳이 없어 큐가 빈 상황 + 벽 부술 수 있는 기회 존재
if(Q.empty() && one_shot) {
for(int dirx = 0; dirx < 4; dirx++) {
int nx = cur.X + dx[dirx];
int ny = cur.Y + dy[dirx];
for(int dir = 0; dir < 4; dir++) {
int px = nx + dx[dir];
int py = ny + dy[dir];
if(px < 0 || px >= N || py < 0 || py >= M) continue;
if(dist[px][py] > 0 || board[px][py] == 1) continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
dist[px][py] = dist[nx][ny]+1;
Q.push({px, py});
one_shot = 0;
}
}
}
// 최단거리 계산
if(dist[N-1][M-1]) {
cout << dist[N-1][M-1];
return 0;
}
}
cout << -1;
return 0;
}코드를 구현하면서도 반례가 있을 것이라 생각했지만, 일단 해보자는 마음에 해봤지만 결국은 실패.. 포기했다..
해답을 보니 핵심아이디어는
방문 표시 배열에 벽 부수기 여부를 추가함으로써 3차원 배열로 구현한다!
결국에는 벽을 부수든, 부수지 않든 최단거리로만 가면 되기 때문에
벽을 부수지 않은 세계와 벽을 부순 세계를 나누어 완전히 독립된 세계로 계산을 해준 뒤, 최단거리를 출력해준다.
해답을 보니 도저히 생각 못했을 아이디어다..
해답 코드
처음에는 해답을 보고도 이해가 가지 않았다.
결국 종이에 하나하나 적어가며 진행을 한 결과 꾸역꾸역 이해했다.
한 좌표에서 갈 수 있는 좌표가 있고, 그 갈 수 있는 좌표에서도 갈 수 있는 좌표가 나누어진다. 그리고 모든 좌표에 벽 부숨 여부를 넣어준다.
예를 들어
a 좌표로 갈 때 벽이 있는 곳(1)을 방문한다면 그 벽을 부수고 거리 기록하고 방문표시를 남기고 좌표는 벽 부숨을 1로 기록한다. 이 좌표를 조상으로 두는 경로는 모두 벽 부숨(1)으로 기록되기 때문에 다시는 벽을 부수지 못한다. 즉 벽 부수는 순간 그 이후부터 벽 부쉈다는 낙인이 찍혀, 벽 부수지 않으면이라는 if 조건에 해당하지 않고 통과된다.
b좌표는 아직 벽을 부수지 않은 좌표며 다른 좌표로 이동하는데, 벽을 만났다. 그 벽 좌표의 벽 부순 좌표의 방문 표시가 없으면 그 벽을 부숴보면서 거리를 기록한다. 그리고 똑같이 벽을 부순 b좌표와 b좌표를 조상으로 둔 좌표들은 다시는 벽을 부수지 못한다. 벽 부쉈다는 낙인이 찍혔기 때문이다.
또 다른 c 좌표도 똑같이 벽 부숴본적이 없으면서 벽을 만났고, 벽을 부숴서 온 좌표의 방문표시가 없다면 벽을 부숴보면서 거리를 기록한다.
이렇게 거리를 기록한다.
그리고 큐를 삭제하는 과정 이전에 내가 가려는 곳의 거리가 제일 먼저 측정되는 순간 그 값을 출력해주면 된다.
다음에 이런 문제가 나오면 꼭 맞춰야겠다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
string board[1002];
int dist[1002][1002][2];
bool OOB(int a, int b) {
return a < 0 || a >= n || b < 0 || b >= m;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> board[i];
queue<tuple<int, int ,int>> Q;
// 출발지 거리도 포함 => 1로 표시
dist[0][0][0] = dist[0][0][1] = 1;
Q.push({0, 0, 0});
while(!Q.empty()) {
int x, y, broken;
tie(x, y, broken) = Q.front();
// broken 여부와 상관없이 최단거리 출력
if(x == n-1 && y == m-1) {
cout << dist[x][y][broken];
return 0;
}
Q.pop();
// 다음 거리
int nextdist = dist[x][y][broken]+1;
for(int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if(OOB(nx, ny)) continue;
if(board[nx][ny] == '0' && dist[nx][ny][broken] == 0) {
dist[nx][ny][broken] = nextdist;
Q.push({nx, ny, broken});
}
if(!broken && board[nx][ny] == '1' && dist[nx][ny][1] == 0) {
dist[nx][ny][1] = nextdist;
Q.push({nx, ny, 1});
}
}
}
cout << -1;
return 0;
}