[ 백준 / 16197 ] 두 동전 (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : 시뮬레이션, 재귀
풀이 시간 : 36분 

문제 풀이 

두 동전은 상하좌우로 이동이 가능하고, 두 동전은 항상 같은 방향으로 이동한다. 단, 새로운 좌표가 벽이라면 이동이 불가능하다. 

동전이 한 개만 남기 위한 최소 이동 횟수는 몇 번인지 구해보자. 

 

먼저, 좌표의 범위를 확인해본다면, $0 ≤ N, M ≤ 20$으로, 재귀함수로 충분히 접근이 가능해 보인다. 또한, 문제의 마지막 조건을 확인해보면, "버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다." 라는 내용이 존재하기 때문에, 시간초과는 신경쓰지 않고 문제에 접근이 가능하다. 시간복잡도를 계산해본다면, 재귀적으로 최대 10번 들어갈 수 있기 때문에, $O(4^11)$가 된다.

 

재귀적으로 문제를 진행하며 걸어준 조건은 다음과 같다.

1. 각각의 동전에 대해 범위를 벗어난 동전이 몇 개나 있는가 ?

2. 새롭게 이동하려는 위치가 벽인가 ?

 

이후, 다음 재귀로 넘어갈 때, 동전들이 아직 살아있고, 두 동전이 모두 움직였는지에 대해 판단하여 다음 재귀를 수행해주었다.

 

코드

/*
버튼은 네가지가 존재함.
버튼을 누르면 두 동전이 같은 방향으로 이동

- 이동하려는 칸이 벽면이면, 동전 이동 불가
	-> 동전이 겹치면 안되는 것에 주의
- 이동 방향에 칸이 없으면, 동전 떨어짐
- 그 외 경우에는, 이동하려는 방향마다 한 칸 이동함

재귀함수로 진행
*/

#include <iostream>
#include <vector>
#include <algorithm>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, m;
char grid[21][21];
int answer = 40000;

int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };

int check_move(int r, int c) {
	if (0 <= r && r < n && 0 <= c && c < m)
		return 1;
	return 0;
}

void dfs(int depth, pair<int, int> coin1, pair<int, int> coin2, int alive) {
	// 종료조건
	if (answer < depth || depth > 10)
		return;
	// 완료조건
	if (alive == 1) {
		answer = depth;
		return;
	}
	// dfs 시작
	pair<int, int> ncoin1, ncoin2;
	for (int d = 0; d < 4; d++) {
		ncoin1.first = coin1.first + dr[d];
		ncoin1.second = coin1.second + dc[d];
		ncoin2.first = coin2.first + dr[d];
		ncoin2.second = coin2.second + dc[d];
		
		int new_alive = check_move(ncoin1.first, ncoin1.second) + check_move(ncoin2.first, ncoin2.second);
		int move_flag = 0;
		if (grid[ncoin1.first][ncoin1.second] == '#') {
			ncoin1 = coin1;
			move_flag++;
		}
		if (grid[ncoin2.first][ncoin2.second] == '#') {
			ncoin2 = coin2;
			move_flag++;
		}

		if (move_flag < 2 && new_alive)
			dfs(depth + 1, ncoin1, ncoin2, new_alive);
	}
}

int main() {
	INIT;
	cin >> n >> m;
	vector<pair<int, int>> coins;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'o') {
				coins.push_back({ i, j });
				grid[i][j] = '.';
			}
		}
	}

	dfs(0, coins[0], coins[1], 2);

	if (answer == 40000)
		answer = -1;
	cout << answer << '\n';

}

배운 점 

오랜만에 시뮬레이션 문제를 풀어보니 재밌기도 하고, 손에 잘 익지 않는 느낌이 든다. 

상반기 코딩테스트를 위해서 다시 하나하나 공부가 필요할 것으로 생각된다.