백준 16197번 두 동전 (C++)

문제 링크 : www.acmicpc.net/problem/16197

16197번: 두 동전

문제 풀이는 다음과 같다.

1. 문자형 타입을 입력받을 배열, 2개의 동전의 방문여부를 동시에 확인할 4*4배열(타입은 int,bool 무엇이든 상관없음)을 생성한다.

동전의 위치값 2개 * 동전 2개 이므로, 방문여부는 4개의 값을 한꺼번에 입력받을 수 있어야한다.

2. BFS를 진행한다. 이때 조건은 크게 4가지로 분류한다.

 

[두 동전의 다음 위치 탐색 없이]

(1) 두 동전 모두 벽에 부딪치는 경우 -> 곧 바로 다음 for문 진행

 

[두 동전의 다음 위치 탐색 후]

(1) 두 동전 모두 밖으로 떨어졌다 -> 곧 바로 다음 for문 진행

(2) 두 동전 중 1개가 밖으로 떨어졌다 -> 10번을 초과하지 않았으면 정답을, 초과했으면 -1을 반환한다.

(3) 위의 두 케이스에 해당되지 않은 경우 (위치 탐색에서 0을 반환) -> 벽에 부딪치는 경우가 있으면 각각 원래자리로 되돌려준다. 그런 다음 해당 위치들이 (동시에) 방문한 적이 있는지를 확인하고, 없을 경우 큐에 삽입해준다.

 

#include <iostream>
#include <algorithm>
#include <queue>
const int MAX = 21;
using namespace std;

int dy[] = {0,0,1,-1}, dx[] = {1,-1,0,0}, n=0, m=0, temp = 0;
char arr[MAX][MAX];
bool ch[MAX][MAX][MAX][MAX] = {false,};
pair<int,int> coin[2];

struct c{
    int y1,x1;
    int y2,x2;
    int cnt;
};

int sway(int y1, int x1, int y2, int x2){
    if((y1<1||y1>n||x1<1||x1>m)&&(y2<1||y2>n||x2<1||x2>m)) return -1; // 동전 둘다 아웃
    if(y1<1||y1>n||x1<1||x1>m) return 1; // 동전 1개 아웃
    if(y2<1||y2>n||x2<1||x2>m) return 1; // 동전 1개 아웃
    return 0;
}

int bfs(){
    queue<c> q;
    q.push({coin[0].first,coin[0].second,coin[1].first,coin[1].second,0});
    while(!q.empty()){
        c cur = q.front();
        int y1=cur.y1; int x1=cur.x1;
        int y2=cur.y2; int x2=cur.x2;
        int now=cur.cnt;
        ch[y1][x1][y2][x2] = true;
        q.pop();
        for(int i=0; i<4; i++){
            int ny1 = y1+dy[i]; int nx1 = x1+dx[i];
            int ny2 = y2+dy[i]; int nx2 = x2+dx[i];
            if(arr[ny1][nx1]=='#'&&arr[ny2][nx2]=='#') continue; // 벽에 부딪쳤으면 아래 공식은 무시하고 다시 for문으로 복귀
            temp = sway(ny1,nx1,ny2,nx2);
            if(temp==-1) continue;
            if(temp==1){
                if(now+1>10) return -1;
                else return now+1;
            } 
            // 아래부터는 각각 벽에 부딪치는 경우 -> 원래 자리로 되돌려주기
            if(arr[ny1][nx1]=='#') ny1-=dy[i], nx1-=dx[i];
            else if(arr[ny2][nx2]=='#') ny2-=dy[i], nx2-=dx[i];
            if(!ch[ny1][nx1][ny2][nx2]){
                q.push({ny1,nx1,ny2,nx2,now+1});
            }
        }
    }
    return -1;
}

void input(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
            if(arr[i][j]=='o'){
                coin[temp].first=i, coin[temp].second=j;
                temp++;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    input();
    cout << bfs() << "\n";
    return 0;
}