문제
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가 일어나서 시간초과가 됐었다.