[백준 17267][BFS][C++] 상남자

https://www.acmicpc.net/problem/17267

17267번: 상남자

 

 

처음 봤을 때, BFS문제인 것은 쉽게 유추할 수 있었지만, 쉽게 틀릴 수 있는 문제였다.

일반적인 BFS처럼 상하좌우 한칸씩  탐색해가며 푼다고 가정했을 때, 반례를 생각해보자.

 

 

(검은색은 벽, 주황색은 처음 위치)

위 8*5 지도에서, 왼쪽으로 한 칸, 오른쪽으로 네 칸 움직일 수 있다.

여기서부터, 한칸씩 탐색해보자.

 

이렇게 20의 결과가 나온다. 하지만 정답은 21인데,

이렇게 가는 방법 또한 있기 때문이다. 즉, 위로 돌아가는 길이 더 짧았기 때문에, 아래로 돌아가는 도중 막혀 갈 수 없었던 것이다.

그렇다면 어떻게 해야할까.

 

상남자는 위 아래로는 무한정 갈 수 있기 때문에, 위 아래를 먼저 최대한 탐색해주면 된다.

위의 반례로 최대한의 위 아래를 먼저 가주는 방법으로 탐색해보자.

 

다음과 같이 정상적으로 21칸을 모두 탐색하는 것을 볼 수 있다.

 

 

#include<iostream>
#include<queue>
using namespace std;

int n,m,l,r, map[1000][1000];
int arx[4]={-1,1,0,0};
int ary[4]={0,0,-1,1};
bool check[1000][1000]={false,};
queue<pair<int,pair<int,pair<int,int> > > > qu; // 좌표x, 좌표y, 왼쪽 이동 가능 수, 오른쪽 이동 가능 수

void push(int a, int b, int c, int d) {qu.push({a,{b,{c,d}}});}

int main(){
    cin>>n>>m>>l>>r;
    for(int i=0; i<n; i++){
        for(int k=0; k<m; k++){
            scanf("%1d",&map[i][k]);
            if(map[i][k]==2){ // 처음 출발 위치
                push(i,k,l,r);
                check[i][k]=true;
            }
        }
    }
    int counter = 1; // 시작위치를 포함하기에 1부터 시작
    while(!qu.empty()){
        int x = qu.front().first, y = qu.front().second.first,
        left = qu.front().second.second.first,
        right = qu.front().second.second.second;
        qu.pop();
        for(int i=0; i<2; i++){ // 위아래 전부 탐색
            int nx = x, ny = y;
            
            while(nx>=0 && nx<n){
                nx += arx[i];
                if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                if(map[nx][ny]==1) break;
                if(check[nx][ny]==false && map[nx][ny]!=1){
                    check[nx][ny]=true;
                    push(nx,ny,left,right);
                    counter ++;
                }
            }
        }
        for(int i=2; i<4; i++){ //좌우 한칸씩 탐색
            int nx = x, ny = y+ary[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(i==2 && left==0) continue;
            if(i==3 && right==0) continue;
            if(check[nx][ny]==false && map[nx][ny]!=1){
                check[nx][ny]=true;
                if(i==2) push(nx,ny,left-1,right);
                else push(nx,ny,left,right-1);
                counter ++;
            }
        }
    }
    cout<<counter;
}