백준 16197 C++ 두 동전

문제

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

풀이

동전이 2개 있는데 하나만 table 밖으로 밀어내야 하는 문제.
하나만 밖으로 보내기 위해선

• 두 동전이 겹치면 안됨(겹치면 둘 다 떨어지거나 둘 다 table위에 남거나 밖에 없기 때문에)

bfs로 모든 경우를 검사하고 위 예외만 처리하면 시간초과없이 해결

코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
char table[21][21];
struct qData {
  pair<int, int> coin1, coin2;
  int depth;
};

pair<int, int> c1, c2;
bool bC1= false;

bool isOutside(int x, int y) {
  if(0 > x || x >= M) {
    return true;
  }
  if(0 > y || y >= N) {
    return true;
  }
  return false;
}

int main(void) {
  cin >> N >> M;
  for(int y=0;y<N;++y) {
    for(int x=0;x<M;++x) {
      cin >> table[y][x];
      if(table[y][x] == 'o') {
        if(bC1) {
          c2 = make_pair(x, y);
        } else {
          c1 = make_pair(x, y);
          bC1 = true;
        }
      }
    }
  }

  queue<qData> q;
  qData initQData;
  initQData.coin1 = c1;
  initQData.coin2 = c2;
  initQData.depth = 0;
  q.push(initQData);
  int dx[4] = {1,-1,0,0};
  int dy[4] = {0,0,1,-1};
  while(!q.empty()) {
    pair<int, int> coin1 = q.front().coin1;
    pair<int, int> coin2 = q.front().coin2;
    int depth = q.front().depth;
    q.pop();
    for(int k=0;k<4;++k) {
      int nextC1X = coin1.first + dx[k];
      int nextC1Y = coin1.second+ dy[k];
      int nextC2X = coin2.first + dx[k];
      int nextC2Y = coin2.second+ dy[k];
      int outsideCnt = 0;
      if(isOutside(nextC1X, nextC1Y)) {
        outsideCnt++;
      }
      if(isOutside(nextC2X, nextC2Y)) {
        outsideCnt++;
      }
      if(outsideCnt == 1) {
        cout << depth+1;
        return 0;
      }
      if(outsideCnt == 0) {
        pair<int, int> nextC1 = make_pair(nextC1X, nextC1Y);
        pair<int, int> nextC2 = make_pair(nextC2X, nextC2Y);
        if(table[nextC1Y][nextC1X] == '#') {
          nextC1 = coin1;
        } 
        if(table[nextC2Y][nextC2X] == '#') {
          nextC2 = coin2;
        } 
        if(nextC1X == nextC2X && nextC1Y == nextC2Y) {
          continue;
        }
        if(depth != 9) {
          qData nextQData;
          nextQData.coin1 = nextC1;
          nextQData.coin2 = nextC2;
          nextQData.depth= depth+1;
          q.push(nextQData);
        }
      }
    }
  }
  cout << -1 << endl;
  return 0;
}