BFS

백준 2206 벽 부수고 이동하기 문제풀이

[2206 벽 부수고 이동하기] https://www.acmicpc.net/problem/2206 .
BFS로 최단거리를 탐색한다.

문제상황 파악하기.

전형적인 그래프 탐색 문제처럼 보인다.
최단거리를 구해야하므로 DFS가 아닌 * BFS(너비우선 탐색) 으로 풀어야한다.

문제는 벽을 한번만 부술수 있다는 것, 그리고 마지막까지 못갈 수도 있다는 점을 파악하고 문제를 풀어보자!

BFS가 뭐길래?

최단거리 문제이기에 BFS로 접근했는데 BFS(Breadth First Search)가 무엇이길래 최단거리르 구할 수 있을까?
BFS는 한 정점에서 가까운 곳부터 순서대로 방문하는 알고리즘이다.
예시는 아래 그림과 같다.

그렇다면 큐를 이용해서 BFS를 구현하고 문제를 풀어보자!

아이디어 얻기.

나는 벽을 부수는 것을 캐릭터가 한다고 생각해서 Player Class를 만들었다.

class Player{
public:
    int item=1; //벽 부수는 아이템
    int y, x;   //위치
};

그리고 이 플레이어들을 queue에 넣어주면 풀 수 있을 거라 생각했다.
왜냐하면 이 플레이어들은 각각 독립되어 있다고 생각했기 때문이다.

주의할 점

하지만 문제가 생겼다!! 플레이어들이 각각 독립적이라 생각했지만 방문처리는 동시에 하는 문제가 있었다.
** 즉, 벽을 안부수고 간 player가 갔던 자리를 벽을 부수고 간 다른 player가 방문을 안하는 문제가 생긴것이다.

아이고…그러니깐 이문제는 벽을 부수고 간 자리인지 아닌지에 따라 방문처리를 해야하는 것이다.
고생한 반례 하나 뿌리고 가겠다.
3 6
010000
010111
000110
ans : 12

**현재 상태를 정점을 만들고 방문처리를 한다.

마지막에 어떤 값이 최소값인지 판단해야하므로 벽을 뚫고 간것 안뚫고 간것을 모두 비교해서 출력해주는 것도 필요하다.

실제 코드

player가 item을 보유하고 있는가 아닌가에 따라 현재 상태를 분류했다.
게임을 좋아하는 나에겐 이 편이 더 직관적이였기 때문이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};

class Player{
public:
    int item=1; //벽 부수는 아이템
    int y, x;   //위치
};

int n,m;
vector<vector<int>> map;
vector<vector<vector<int>>> dist;

void bfs(){
    Player start;
    start.y = 0; start.x = 0;
    
    queue<Player> q;
    q.push(start);
    dist[start.y][start.x][1] = 1;
    
    while (!q.empty()) {
        Player here = q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            if(here.y+dy[i]>=0&&here.y+dy[i]<map.size()&&here.x+dx[i]>=0&&here.x+dx[i]<map[0].size()){
                Player p;
                p.y = here.y+dy[i]; p.x = here.x +dx[i]; p.item = here.item;
                if(map[p.y][p.x]==0&&dist[p.y][p.x][p.item]==-1){
                    q.push(p);
                    dist[p.y][p.x][p.item] = dist[here.y][here.x][here.item]+1;
                }else if(map[p.y][p.x]==1&&dist[p.y][p.x][p.item]==-1&&p.item){
                    p.item--;
                    dist[p.y][p.x][p.item] = dist[here.y][here.x][here.item]+1;
                    q.push(p);
                }
            }
        }
    }
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    cin >> n >> m;
    
    map = vector<vector<int>> (n, vector<int>(m));
    dist = vector<vector<vector<int>>> (n, vector<vector<int>> (m,vector<int> (2,-1)));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char ch;
            cin >> ch;
            map[i][j] = ch-'0';
        }
    }
    
    bfs();
    if(dist[n-1][m-1][1]!=-1&&dist[n-1][m-1][0]!=-1) cout << min(dist[n-1][m-1][1],dist[n-1][m-1][0]);
    else if(dist[n-1][m-1][1]!=-1) cout << dist[n-1][m-1][1];
    else if(dist[n-1][m-1][0]!=-1) cout << dist[n-1][m-1][0];
    else cout << dist[n-1][m-1][0];
}