[C++] 백준 16197번: 두 동전

문제 링크

16197번: 두 동전

문제 요약

보드 상에 동전 두 개가 있다. 동전은 벽이 없는 칸으로 이동할 수 있다.
이동하고자 하는 칸에 동전이 있어도 이동이 가능하다.
이 동전을 상하좌우로 이동시켜 하나만 떨어뜨리기 위한 최소 횟수를 구해야 한다.
10회를 넘어가면 -1을 출력한다.

접근 방법

단순 구현 문제였지만 구조체를 남발해서 코드가 복잡해지고 가독성이 너무 떨어져서 전부 지우고 다시 구현하느라 시간이 좀 오래 걸렸습니다.

재방문을 확인하는 배열을 4차원으로 선언해주고 기존 BFS와 비슷하게 작성을 해주면 됩니다. 단, 이동하고자하는 칸이 벽인 경우의 처리가 조금 다릅니다. 일단 이동을 시켜보고, 벽이라면 원래 위치로 재이동 시켜주면 됩니다. 다른 동전은 이동이 가능할 수도 있기 때문입니다. 둘 다 벽에 직면하는 경우에는 재방문 여부를 체크할 때 어차피 걸리게 되기 때문에 문제가 없습니다.

동전이 떨어지는 여부도 확인을 해야하는데, 만약 하나가 떨어지면 즉시 값을 반환하고, 2개가 떨어진다면 continue로 건너뛰어주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int r1, c1, r2, c2, cnt;
};

int n, m, dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool visited[21][21][21][21];
char b[21][21];

bool move(int& nr, int& nc, int r, int c, int d)
{
	nr = r + dir[d][0];
	nc = c + dir[d][1];

	if (nr < 1 || nr > n || nc < 1 || nc > m)
		return true;

	if (b[nr][nc] == '#')
	{
		nr = r;
		nc = c;
	}

	return false;
}

int bfs(Data s)
{
	queue<Data> q;
	q.push(s);
	visited[s.r1][s.c1][s.r2][s.c2] = true;

	while (!q.empty())
	{
		Data now = q.front();
		q.pop();

		if (now.cnt >= 10)
			break;

		for (int i = 0; i < 4; i++)
		{
			Data next;
			int cnt = 0;
			if (move(next.r1, next.c1, now.r1, now.c1, i))
				cnt++;
			if (move(next.r2, next.c2, now.r2, now.c2, i))
				cnt++;
			next.cnt = now.cnt + 1;

			if (cnt == 2)
				continue;
			if (cnt == 1 && next.cnt )
				return next.cnt;
			
			if (!visited[next.r1][next.c1][next.r2][next.c2])
			{
				visited[next.r1][next.c1][next.r2][next.c2] = true;
				q.push(next);
			}
		}
	}

	return -1;
}

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

	int idx = 0;
	pair<int, int> coin[2];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> b[i][j];
			if (b[i][j] == 'o')
			{
				coin[idx].first = i;
				coin[idx++].second = j;
				b[i][j] = '.';
			}
		}
	}

	cout << bfs({ coin[0].first, coin[0].second, coin[1].first, coin[1].second, 0 });
	return 0;
}