#16197 두 동전

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

16197번: 두 동전

 

문제

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

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

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

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

 

입력

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

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

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

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

 

출력

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

 

풀이

 

문제에 있는

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

그대로 구현

 

코드

 

	// #16197 두 동전
	//동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
	//동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
	//그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.
	//이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
	#include <iostream>
	#include <queue>
	#include <cstring>
	using namespace std;
	int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };
	int n, m;
	char map[22][22];
	int visit[21][21][21][21];
	typedef struct xy {
	int x, y;
	};
	typedef struct info {
	int x1, y1;
	int x2, y2;
	};
	xy st[2];
	bool move(int*x1, int*y1, int*x2, int*y2,int d,int TIME) {
	//코인 1 먼저 그다음 코인 2
	int sum = 0;//떨어진 횟수
	if (*x1 < 0 || *y1 < 0 || *x1 >= n || *y1 >= m) {
	sum++;
	}
	else if (map[*x1][*y1] == '#') {
	*x1 -= dir[d][0], *y1 -= dir[d][1];
	}
	if (*x2 < 0 || *y2 < 0 || *x2 >= n || *y2 >= m) {
	sum++;
	}
	else if (map[*x2][*y2] == '#') {
	*x2 -= dir[d][0], *y2 -= dir[d][1];
	}
	//둘다 움직일 수 있는 경우
	//둘다 떨어지거나 포개질 경우
	if (*x1 == *x2&&*y1 == *y2||sum==2)return false;
	else if (sum == 1) {
	//하나만 떨어질 경우
	cout << TIME+1 << endl;
	exit(0);
	}
	return true;
	}
	void bfs() {
	queue<info>q;
	q.push({ st[0].x,st[0].y,st[1].x,st[1].y });
	visit[st[0].x][st[0].y][st[1].x][st[1].y] = true;
	int TIME = 0;
	while (!q.empty()) {
	int sz = q.size();
	while (sz--) {
	int fx1 = q.front().x1, fy1 = q.front().y1;
	int fx2 = q.front().x2, fy2 = q.front().y2;
	q.pop();
	//cout << "fx1 " << fx1 << " fy1 " << fy1 << " fx2 " << fx2 << " fy2 " << fy2 << endl;
	for (int d = 0; d < 4; d++) {
	int nx1 = fx1 + dir[d][0], ny1 = fy1 + dir[d][1];
	int nx2 = fx2 + dir[d][0], ny2 = fy2 + dir[d][1];
	bool tf=move(&nx1, &ny1, &nx2, &ny2,d,TIME);
	if (!tf)continue;
	if (visit[nx1][ny1][nx2][ny2])continue;
	visit[nx1][ny1][nx2][ny2] = true;
	q.push({ nx1,ny1,nx2,ny2 });
	}
	}
	TIME++;
	if (TIME >= 10)break;
	}
	cout << -1 << endl;
	}
	int main() {
	cin >> n >> m;
	int idx = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	cin >> map[i][j];
	if (map[i][j] == 'o') {
	st[idx++] = { i,j };
	}
	}
	}
	bfs();
	}

view raw [BOJ]16197 두 동전.cpp hosted with ❤ by GitHub