[백준] 2206: 벽 부수고 이동하기

url : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

일반적인 bfs 문제에서 조건이 추가된 문제이다.

벽을 한 개 이하로 부실 수 있는데, 벽을 부순 수를 visited 배열에 추가하여 최단거리를 계산하면 된다.

 

벽 부순 상태를 저장하는 이유

벽을 부순 상태에서 도달했을 때와, 벽을 부수지 않고 도달했을 때 각각 다른 결과를 불러올 수 있기 때문이다.

아래 예시는 질문게시판에 올라온 예시인데 이해하기 쉬워 가져왔다.

 

입력

6 6

000000

011111

011111

010100

010110

000110

 

정답

15

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, x, y, cnt;
string s;
int mp[1004][1004];
int visited[1004][1004][2]; // y x cnt
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

void bfs(){
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});
    visited[0][0][0]=1;
    while(!q.empty()){
        tie(y, x, cnt) = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<0||nx<0||ny>=n||nx>=m) continue;
            if (mp[ny][nx]==0 && visited[ny][nx][cnt]==0){
                visited[ny][nx][cnt] = visited[y][x][cnt]+1;
                q.push({ny, nx, cnt});
            } 
            // 벽 부시기
            if(mp[ny][nx]==1 && cnt==0 && visited[ny][nx][1]==0){
                visited[ny][nx][1] = visited[y][x][cnt]+1;
                q.push({ny, nx, 1});
            }
        }
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    // 1. 입력받기
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> s;
        for(int j=0;j<m;j++){
            mp[i][j] = s[j]-'0';
        }
    }
    // 2. bfs 수행
    bfs();
    // 3. 정답 출력
    int ans1 = visited[n-1][m-1][0];
    int ans2 = visited[n-1][m-1][1];
    if(ans1==0 && ans2==0) cout << -1;
    else if (ans1==0) cout << ans2;
    else if (ans2==0) cout << ans1;
    else cout << min(ans1, ans2); 
}