[백준] 16197번 - 두 동전 / C++

문제

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

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

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

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

 

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

 

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

코드

#include <iostream>

using namespace std;

int N;
int M;
bool board[21][21];		// 0: 칸, 1: 벽
int dn[] = {-1, 1, 0, 0};	// 0: UP, 1: DOWN, 2: LEFT, 3: RIGHT
int dm[] = {0, 0, -1, 1};	// 0: UP, 1: DOWN, 2: LEFT, 3: RIGHT
int answer = 11;

// 동전이 보드 위에 있는지 확인
bool is_on(int y, int x)
{
	if (y < 1 || y > N || x < 1 || x > M)
		return false;
	return true;
}

void dfs(int cnt, int y1, int x1, int y2, int x2)
{
	int i;
	int dy1, dx1, dy2, dx2;

	if (cnt > 10)
		return;
        
	// 두 동전 중 하나만 보드 위에 있는 경우
	if (is_on(y1, x1) != is_on(y2, x2))
	{
		answer = min(answer, cnt);
		return;
	}
    
	for (i = 0; i < 4; i++)
	{
		dy1 = y1 + dn[i];
		dx1 = x1 + dm[i];
		dy2 = y2 + dn[i];
		dx2 = x2 + dm[i];
        
		// 두 동전 모두 떨어진 경우
		if (!(is_on(dy1, dx1) || is_on(dy2, dx2)))
			continue;
        
		// 다음 위치가 벽이면 기존 위치 유지
		if (is_on(dy1, dx1) && board[dy1][dx1])
		{
			dy1 = y1;
			dx1 = x1;
		}
		if (is_on(dy2, dx2) && board[dy2][dx2])
		{
			dy2 = y2;
			dx2 = x2;
		}
        
		dfs(cnt + 1, dy1, dx1, dy2, dx2);
	}
}

int main()
{
	int i, j, k = 0;
	int c[2][2];
	string s;

	cin >> N >> M;
	for (i = 1; i <= N; i++)
	{
		cin >> s;
		for (j = 0; j < M; j++)
		{
			if (s[j] == '#')
			{
				board[i][j + 1] = 1;
				continue;
			}
			if (s[j] == 'o')
			{
				c[k][0] = i;
				c[k][1] = j + 1;
				k++;
			}
			board[i][j + 1] = 0;	
		}
		s.clear();
	}
	dfs(0, c[0][0], c[0][1], c[1][0], c[1][1]);
	if (answer > 10)
		answer = -1;
	cout << answer << endl;
	return 0;
}

 

링크

16197번: 두 동전

inbdni/Baekjoon