[BOJ] 백준 두 동전 16197번

이번 문제 또한 풀이를 참고하여 풀었습니다. 접근을 하려고 했던 방식은 틀리지 않았는데 동전 두 개의 좌표를 한꺼번에 bfs에 넣어야 된다는 것을 생각하지 못했습니다. 몇 문제 풀다 보니까 백트래킹에 대해서 알듯 말듯한 느낌입니다. 참고한 코드가 짧고 이해하기 편했던 것 같습니다.

풀이 방법

주석에도 간단하게 적어놓긴 했지만 몇 군데 포인트 되는 부분만 설명을 해보겠습니다.

1. 이동하려는 칸이 동전이어도 이동이 가능하기 때문에 입력을 받으면서 'o'일 경우 vector에 넣고, '.'로 바꾸어주었습니다.

2. coin[0]의 first는 1번째 동전의 x좌표, coin[0]의 second는 1번째 동전의 y좌표입니다. 마찬가지고 coin[1]의 first는 두 번째 동전의 x좌표, second는 두 번째 동전의 y좌표입니다.

3. cnt는 버튼을 클릭한 횟수를 의미하며 10번이 넘어갈 경우 return 합니다. 

4. 각각의 동전의 이동할 x, y 좌표를 구합니다. 만약 이동하려는 좌표가 0 <x <=n or 0 <y <=m이라면 밖으로 동전이 떨어진 것을 의미하므로 flag를 사용하여 true로 값을 변경합니다.

5. 두 동전의 flag 상태가 다르다는 것은 둘 중 하나만 떨어졌다는 것이고, cnt를 result 변수에 저장합니다.

6. 이동하려고 하는 위치가 '#'일 경우 이동이 불가능하므로 nx, ny, nxx, nyy에 기존의 좌표를 다시 대입합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define MAXNUM 987654321
using namespace std;

int n, m, result=MAXNUM;
string puzzle[21];
bool check[21][21];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool firstF = false, secondF = false;
vector<pair<int, int>> coin;

void solution(int x, int y, int xx, int yy, int cnt) {

	if (cnt > 10) return;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nxx = xx + dx[i];
		int nyy = yy + dy[i];

		firstF = false; secondF = false;

		// 동전이 떨어지면 true가 됨
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) firstF = true;

		if (nxx < 0 || nxx >= n || nyy < 0 || nyy >= m) secondF = true;
		
		if (firstF == !secondF) {
			// 두 개의 flag가 다를 경우(동전이 하나만 떨어졌을 경우)
			result = min(result, cnt);
		}

		if (firstF || secondF) continue;

		if (puzzle[nx][ny] == '#') { //다음 위치가 #일 경우 기존 위치로
			nx = x;
			ny = y;
		}

		if (puzzle[nxx][nyy] == '#') {
			nxx = xx;
			nyy = yy;
		}

		solution(nx, ny, nxx, nyy, cnt + 1);

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

	for (int i = 0; i < n; i++) {
		cin >> puzzle[i];
		for (int j = 0; j < m; j++) {
			if (puzzle[i][j] == 'o') {
				coin.push_back(make_pair(i,j));
				puzzle[i][j] = '.'; // 동전이 있는 곳에도 갈 수 있으니까
			}
		}
	}

	solution(coin[0].first, coin[0].second, coin[1].first, coin[1].second, 1);

	if (result == MAXNUM)
		cout << -1 << '\n';
	else
		cout << result << '\n';
	

}