[G4] 백준 16197번 두 동전 C++ 너비 우선 탐색

리뷰

 

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

두 동전을 동시에 움직여 하나의 동전만 맵 밖으로 이동하게 만드는 최소 이동 횟수를 구하는 문

 

 

전역 변수

• n : 맵의 세로 길이를 저장할 변수
• m : 맵의 가로 길이를 저장할 변수
• lst : 맵 정보를 저장하기 위한 문자열 타입의 배열
• v : 각 동전의 위치를 통해 방문 처리를 위한 논리형 4차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Coin : 두 코인의 위치 좌표와 소요 시간을 정의하기 위한 구조체

 

함수

1. bfs

int bfs(const Coin& s)

 

너비 우선 탐색을 통해 한개의 코인만 맵 밖으로 나간 최소 시간을 구하기 위한 함수

1. 매개변수로 초기 코인의 위치를 정의한 Coin 타입의 변수 s를 전달 받는다.
2. Coin타입의 큐 q를 초기화 하고, q에 s를 push해준다.
3. 초기 동전의 위치에 대해 방문처리를 진행해 준다.
4. q가 빌 때 까지 while루프를 수행하고, 각 루프마다 요소를 한개씩 꺼내어 준다.
5. 만약 현재 소요시간이 10이상일 경우 continue처리를 진행해 준다.
6. 4방향 탐색을 진행하며 두 동전을 동일한 방향으로 이동을 진행한다.
7. 정수형 변수 flag1, flag2를 모두 0으로 초기화 해준다.
8. 만약 동전 1이 맵을 벗어났으면 flag1을 1로 초기화, 동전 2가 맵을 벗어났으면 flag2를 1로 초기화 한다.
9. 기저 조건으로 flag1과 flag2를 XOR 연산환 결과가 1이라면 현재 소요시간 + 1을 리턴해 준다.
10. 기저 조건에 해당하지 않는다면 flag1, flag2를 다시 0으로 초기화 해준다.
11. 각각의 동전이 이동한 좌표가 맵의 범위 안에 있다면 flag를 1로 변경해 준다.
12. 추가로, 이동한 위치가 벽이라면 이동 위치를 다시 원래 위치로 변경해 준다.
13. flag1과 flag2를 곱한 값이 0이라면 continue를 수행해 준다.
14. 동전 두개의 위치가 방문 처리 되어 있다면 continue를 수행해 준다.
15. 위 조건에 걸리지 않는다면 두 동전의 위치를 방문처리 후 q에 두 동전의 위치와 소요 시간을 증가시켜 push한다.
16. 만약 while루프 내에 기저 조건에 도달하지 못한 경우 -1를 리턴한다.

 

문제풀이

1. n, m값을 입력 받고, 초기 동전 위치를 저장할 Coin 타입의 변수 coin의 모든 값을 0으로 초기화 해준다.
2. 정수형 변수 index를 0으로 초기화 해준다.
3. n줄의 맵 정보를 문자열 배열 lst에 입력 받아준다.
4. 각 문자를 탐색하며 'o'를 만난 경우 맵상에서의 값을 '.'로 변경해 준다.
5. 이후 index가 0인 경우 첫번째 코인의 위치 정보를 저장해 주고 index를 증가시켜 준다.
6. index가 1인 경우 두번째 코인의 위치 정보를 저장해 준다.
7. bfs함수에 coin을 매개변수로 전달하여 리턴 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다.
• 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.
• 벽을 만난 경우 방문처리를 진행해 주면 안된다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, m;
string lst[20];
bool v[20][20][20][20];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Coin {
	int x1, y1, x2, y2, t;
};

int bfs(const Coin& s) {
	queue<Coin> q;
	q.push(s);
	v[s.x1][s.y1][s.x2][s.y2] = 1;

	while (!q.empty()) {
		Coin coin = q.front(); q.pop();
		int cx1 = coin.x1, cy1 = coin.y1, cx2 = coin.x2, cy2 = coin.y2, ct = coin.t;
		if (ct >= 10) continue;

		for (int i = 0; i < 4; ++i) {
			int nx1 = cx1 + dx[i], ny1 = cy1 + dy[i], nx2 = cx2 + dx[i], ny2 = cy2 + dy[i], nt = ct + 1;
			
			int flag1 = 0, flag2 = 0;
			if (0 > nx1 || nx1 >= n || 0 > ny1 || ny1 >= m) flag1 = 1;
			if (0 > nx2 || nx2 >= n || 0 > ny2 || ny2 >= m) flag2 = 1;
			if (flag1 ^ flag2) return nt;

			flag1 = 0, flag2 = 0;
			if (0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m) {
				flag1 = 1;
				if (lst[nx1][ny1] == '#') nx1 = cx1, ny1 = cy1;
			}

			if (0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m) {
				flag2 = 1;
				if (lst[nx2][ny2] == '#') nx2 = cx2, ny2 = cy2;
			}

			if (flag1 * flag2 == 0) continue;
			if (v[nx1][ny1][nx2][ny2]) continue;
			v[nx1][ny1][nx2][ny2] = 1;
			q.push({ nx1, ny1, nx2, ny2, nt });
		}
	}
	return -1;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie();

	cin >> n >> m;
	Coin coin = { 0, 0, 0, 0, 0 };
	int index = 0;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == 'o') {
				lst[i][j] = '.';
				if (!index) {
					coin.x1 = i;
					coin.y1 = j;
					index++;
				}
				else {
					coin.x2 = i;
					coin.y2 = j;
				}
			}
		}
	}
	cout << bfs(coin);
}