[BOJ 16197] 두 동전

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 “왼쪽”, “오른쪽”, “위”, “아래”와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. baekjoon

코드

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int n, m;

int dir_x[] = {1, -1, 0, 0};
int dir_y[] = {0, 0, 1, -1};

int get_min(vector<vector<char>> &v, vector<pair<int, int>> &coins, int move) {
  if (move > 10) return -1;

  // 코인 하나만 빠졌는지 확인
  int down_cnt = 0;
  for (int i = 0; i < 2; i++) {
    if (coins[i].first < 0 || coins[i].second < 0 || coins[i].first >= n || coins[i].second >= m) {
      down_cnt++;
    }
  }
  if (down_cnt == 1) return move;
  if (down_cnt == 2) return -1;
  
  int result = -1;
  for (int i = 0; i < 4; i++) {
    vector<pair<int, int>> new_coins(2);
    pair<int, int> coin1 = make_pair(coins[0].first + dir_x[i], coins[0].second + dir_y[i]);
    pair<int, int> coin2 = make_pair(coins[1].first + dir_x[i], coins[1].second + dir_y[i]);
    bool is_valid1 = coin1.first >= 0 && coin1.second >= 0 && coin1.first < n && coin1.second < m;
    bool is_valid2 = coin2.first >= 0 && coin2.second >= 0 && coin2.first < n && coin2.second < m;

    if (is_valid1 && v[coin1.first][coin1.second] == '#') {
      new_coins[0] = coins[0];
    } else {
      new_coins[0] = coin1;
    }

    if (is_valid2 && v[coin2.first][coin2.second] == '#') {
      new_coins[1] = coins[1];
    } else {
      new_coins[1] = coin2;
    }

    int tmp = get_min(v, new_coins, move + 1);
    if (tmp != -1 && (result == -1 || result > tmp)) {
      result = tmp;
    }
  }
  return result;
}

int main() {
  cin >> n >> m;

  vector<vector<char>> v(n, vector<char>(m));
  vector<pair<int, int>> coins;
  for (int i = 0; i < n; i++) {
    string tmp;
    cin >> tmp;
    for (int j = 0; j < m; j++) {
      v[i][j] = tmp[j];
      if (v[i][j] == 'o') {
        coins.push_back(make_pair(i, j));
      }
    }
  }

  cout << get_min(v, coins, 0);
}

풀이

동전의 위치를 받고, 상하좌우로 움직여서 10번 이내로 동전 1개만 빠지는 경우를 찾도록 했다.
vector를 주소로 안넘겼더니 value copy가 일어나서 시간초과가 됐었다.

Published 16 Oct 2019

Baekjoon