이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 93 번째 글 입니다.
목차
골드4 : bfs 문제이다.
풀이
- bfs는 가중치가 없는 그래프의 최단 거리 문제를 풀 때 사용하는 방법이다.
- 이 문제는 최단 거리 문제이므로 이 풀이를 선택하는 것은 맞다.
- 그런데 생각해보면, 이번에는 해당 칸에 방문했는가를 기준으로 다음 노드를 탐색하는 것으로는 부족하다.
- 특정 칸에 방문할 수 있는 방법은 그냥 도착한다, 벽을 부수고 도착한다. 두가지로 나뉜다.
- 그리고 그 상황에서 다음 칸을 이동할 때에도 도착한 상태에 따라 다음칸을 갈 수 있는지 없는지로 나뉜다.
- 즉, 특정칸에 방문했을 때, 상태가 두가지로 나뉜다는 것이다.
- 종료는 bfs 특성상, 같은 너비인 상태에서(경로 cost가 같은 상태에서) 진행되기 때문에 목표 위치까지 도착하는 순간이 최단 거리이다.
- 그렇다면 q에 넣는 노드의 정보에, 지금 벽을 뚫었는지 여부가 중요하게 된다.
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <queue>
using namespace std;
struct state{
int y, x, blockNum;
};
int N, M;
int graph[1001][1001];
int visited[1001][1001][2];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
bool isIn(int y, int x){
return (1 <= y && y <= N && 1 <= x && x <= M);
}
//void PPP(){
// cout << "=====graph======" << '\n';
// for (int i = 1; i <= N; i++) {
// for (int j = 1; j <= M; j++) {
// cout << graph[i][j] << " ";
// }cout << '\n';
// }
// cout << "=====visited======" << '\n';
// for (int i = 1; i <= N; i++) {
// for (int j = 1; j <= M; j++) {
// cout << visited[i][j][0] << " ";
// }cout << " ";
// for (int j = 1; j <= M; j++) {
// cout << visited[i][j][1] << " ";
// }cout << '\n';
// }
//}
int main(){
cin >> N >> M;
char temp[1001];
for (int i = 1; i <= N; i++) {
cin >> temp;
for (int j = 1; j <= M; j++) {
graph[i][j] = temp[j-1] - '0';
}
}
queue<state> q;
int ans = -1;
state s = {1, 1, 1};
visited[1][1][1] = 1;
q.push(s);
while (!q.empty()) {
state s = q.front();
q.pop();
// PPP();
// 탐색하다가 (N,M)에 가장 먼저 도착하면 그때의 이동거리가 최단거리이다.
if (s.y == N && s.x == M) {
ans = visited[N][M][s.blockNum];
break;
}
for (int i = 0; i < 4; i++) {
int next_y = s.y + dy[i], next_x = s.x + dx[i];
// map안에 있는가?
if (isIn(next_y, next_x)) {
// 다음으로 갈수 있고 방문하지 않았다면 -> 내 blocknum 상태
if (graph[next_y][next_x] == 0 && visited[next_y][next_x][s.blockNum] == 0) {
visited[next_y][next_x][s.blockNum] = visited[s.y][s.x][s.blockNum] + 1;
state sp = {next_y, next_x, s.blockNum};
q.push(sp);
}
// 다음으로 갈수 없지만 아직 벽을 뚫지 않았다면
if (graph[next_y][next_x] == 1 && s.blockNum){
visited[next_y][next_x][s.blockNum-1] = visited[s.y][s.x][s.blockNum] + 1;
state sp = {next_y, next_x, s.blockNum-1};
q.push(sp);
}
// 나머지 경우는 탐색할 필요가 없다.
// 다음으로 갈수 있지만 방문했다면 -> 방문한 녀석은 볼필요 없다.
// 다음으로 갈수 없지만 벽을이미 뚫었다 -> 방문 불가능
}
}
}
cout << ans << '\n';
return 0;
}
//7 8
//01000100
//01010100
//01010100
//01010100
//01010100
//01010100
//00010100