https://www.acmicpc.net/problem/2206
출발지에서 도착지점까지 최단거리를 찾는 전형적인 BFS 문제 풀이이다.
다만, 갈 수 없는 길을 하나 부수고 갈 수 있다는 점을 처리 하기 위해
visited 차원을 하나 추가해서 길을 뚫은 상태인지, 아닌지를 체크하였다.
다음 목적지 map[nx][ny]
갈 수 있는 상태라면, 현재 뚫은 상태를 그대로 가지고 간다.
만약 다음 목적지가 갈 수 없는 상태라면, 현재 뚫은 상태에 따라 달라진다.
visited[nx][ny] [1-curK] = visited[x][y][curK]
현재 상태는 0 아니면 1이기 때문에 1-curK
연산으로 교체해준다.
상태 변수 이름이 curK
인 이유는, 벽 부수고 이동하기 2를 풀다가 건너왔기 때문,,
처음엔 경로의 길이를 queue에 넣어서 풀었지만, 메모리 초과가 났다.
다시 풀어보니 queue에 경로의 길이를 넣어서 메모리 초과가 난건 아니지만,
이미 잡혀있는 visited
메모리를 활용하는게 더 효율적일것같아서 visitied
에 경로의 길이를 저장하였다.
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX = 1000;
int n, m;
int map[MAX][MAX];
int visited[MAX][MAX][2];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int bfs(int sx, int sy, int k) {
// x, y, k
queue<vector<int>> q;
q.push({sx, sy, 0});
while(!q.empty()) {
int x = q.front()[0];
int y = q.front()[1];
int curK = q.front()[2];
q.pop();
if (x == n-1 && y == m-1)
return visited[x][y][curK] + 1;
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)
continue;
if (visited[nx][ny][curK] == 0) {
// 갈수 있는 길, 뚫은 상태 or 안뚫은상태 쭉감
if (map[nx][ny] == 0) {
q.push({nx, ny, curK});
visited[nx][ny][curK] = visited[x][y][curK] + 1;
} else if (curK == 0) { // 못가는데 뚫을 수 있으면
q.push({nx, ny, 1 - curK});
visited[nx][ny][1-curK] = visited[x][y][curK] + 1;
}
}
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
string rows;
for (int i=0; i<n; i++) {
cin >> rows;
for (int j=0; j<m; j++) {
map[i][j] = rows[j] - 48;
}
}
memset(visited, 0, sizeof(visited));
cout << bfs(0, 0, 0);
return 0;
}