[백준] 16197 두 동전

[문제이해]
1. N x M map에는 두 개의 동전(o) 벽(#)과 빈 칸(.)이 존재한다.  (두 동전의 위치는 다름)

2. 두 동전을 동시에 움직일 수 있는 버튼이 있다. (방향은 상하좌우 4방향)

3. 두 동전 중 하나만 map에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구해야한다.

4. 단, 동전을 떨어뜨리거나 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

[설계]
1. x,y 구조체에 대한 구조체를 만들어 두 동전의 위치좌표를 간단하게 표현한다.

2. 4 방향의 버튼을 누르는 경우의 수를 재귀적으로 구현한다.

3. 재귀단계가 10이 넘어가면, 실패 (-1 출력)

4. 한 개의 동전만 떨어졌을때 버튼을 누른 횟수가 최소인지 체크하고, 최소이면 값을 갱신한다.

5. 두 동전이 모두 떨어지면, 실패 (해당 경우의 수 continue로 스킵)

6. 동전이 움직일 다음칸이 벽이라면 이동시키지 말아야한다.

7. 동전의 위치는 빈 칸이라고 생각한다. (문제에 동전이 있는 경우에도 이동한다고 명시, 입력받을때 동전 위치를 . 으로 처리)

8. 재귀적으로 경우의 수를 모두 살펴봤으면, 결과를 출력한다. ( res가 초기값인 1e9라면, 한 개의 동전을 떨어뜨리는 경우의 수가 없었던 것이므로 -1을 출력)

 

[회고]

- 동전이 있는 경우에도 이동할 수 있음을 간과했었다.

- 4차원 check 배열을 통해 이미 알아보았던 경우의 수일 경우 스킵을 하도록 구현 했는데, 굳이 그거까지 고려하지 않아도 됐음

 

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct {
	int x, y;
}pos;

char map[20][20];
int n, m;
int res = 1e9;
vector<pos> coin;
int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};

void dfs(pos a, pos b, int cnt) {

	if (cnt > 10) return;

	for (int i = 0; i < 4; i ++) {
		int nax = a.x + dx[i], nay = a.y + dy[i];
		int nbx = b.x + dx[i], nby = b.y + dy[i];
		bool a_flag = false, b_flag = false;

		if (nax >= n || nax < 0 || nay >= m || nay < 0) a_flag = true; //a동전 떨어짐
		if (nbx >= n || nbx < 0 || nby >= m || nby < 0) b_flag = true; //b동전 떨어짐

		if (a_flag == !b_flag) {
			res = min(res, cnt);
		}
		
		if (a_flag || b_flag) continue;

		if (map[nax][nay] == '#' ) {
			nax = a.x, nay = a.y;
		}

		if (map[nbx][nby] == '#' ) {
			nbx = b.x, nby = b.y;
		}
		dfs({ nax,nay }, { nbx,nby }, cnt + 1);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'o') {
				coin.push_back({ i,j });
				map[i][j] = '.';
			}
		}
	}

	dfs(coin[0], coin[1],1);

	if (res == 1e9)
		cout << -1;
	else
		cout << res;
	return 0;
}

 

[출처]

본인