백준 16197( 두 동전)

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

16197번: 두 동전

해당 문제는 동전이 2개가 존재하며 아래와 같은 규칙을 이용하며 동전이 하나만 떨어지는 최소한의 경우를 구하는 문제이다. 따라서 BFS를 사용한 완전탐색을 이용하여 동전이 떨어질때의 Cnt 값을 반환하는 형식으로 풀이하면 된다.

요구사항 :

동전은 상하좌우로 이동가능하며 최대 10번 까지 이동할 수 있다 초과시 -1 반환

동전이 하나만 떨어질 경우가 없는 경우 -1 반환

동전의 이동방향이 벽일경우 이동 X, 이동방향이 동전일 경우 겹치게 둘 수 있음

 

풀이 :

BFS를 이용하여 동전 1, 동전 2의 좌표와 현재 떨어진 동전의 개수, 현재 이동 횟수를 담는 구조체 Node를 사용하여 풀이한다.

이때 주의해야 할 점이 이미 동전이 방문한 경우는 다시 탐색할 필요가 없으므로 4차원 배열을 사용하여 다음과 같이 Check 한다

visit[동전1 Y][동전 1 X][동전 2 Y][동전 2 X] 좌표를 확인하며 탐색할때 1로 check한 뒤 체크 하지 않은 동전의 좌표일 때만 방문한다면 최소시간으로 탐색가능하다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>


using namespace std;

// 동전 1 좌표, 동전 2 좌표
// 떨어진 동전의 개수, 현재 이동 횟수
struct Node{
	int y1, x1;
	int y2, x2;
	int drop;
	int cnt;
};
vector<Node> vect;
int n, m;
int checkY[4] = { -1, +1, 0, 0 };
int checkX[4] = { 0, 0, -1, +1 };
char map [21][22];
int visit[21][21][21][21];


Node move(Node now, int dir){
	int dy1 = now.y1 + checkY[dir];
	int dx1 = now.x1 + checkX[dir];
	int dy2 = now.y2 + checkY[dir];
	int dx2 = now.x2 + checkX[dir];

	// param 으로 받은 동전1과 2의 이동한 좌표가 만약
	// 범위를 벗어난다면 drop++ 
	// 벽이라면 원 위치
	// 벽이 아니라면 위치값 이동한 좌표로 변경
	if (dy1 < 0 || dx1 < 0 || dy1 >= n || dx1 >= m){
		now.drop++;
		dy1 = -1;
		dx1 = -1;
	}
	else if (map[dy1][dx1] == '#'){
		dy1 = now.y1;
		dx1 = now.x1;
	}

	if (dy2 < 0 || dx2 < 0 || dy2 >= n || dx2 >= m){
		now.drop++;
		dy2 = -1;
		dx2 = -1;
	}
	else if (map[dy2][dx2] == '#'){
		dy2 = now.y2;
		dx2 = now.x2;
	}
	now = { dy1, dx1, dy2, dx2, now.drop, now.cnt + 1 };

	return now;
}

int bfs(){
	queue<Node> qu;
	qu.push(vect[0]);
	visit[qu.front().y1][qu.front().x1][qu.front().y2][qu.front().x2] = 1;

	while (!qu.empty()){
		Node now = qu.front();
		if (now.cnt == 10) return -1;
		for (int i = 0; i < 4; ++i){
			Node tmp = move(now, i);
			// 동전이 하나 떨어진 경우 현재 이동횟수 반환
			if (tmp.drop == 1) return tmp.cnt;
			if (tmp.drop == 2) continue;
			if (tmp.y1 == tmp.y2 && tmp.x1 == tmp.x2) continue;
			if (visit[tmp.y1][tmp.x1][tmp.y2][tmp.x2] == 0){
				visit[tmp.y1][tmp.x1][tmp.y2][tmp.x2] = 1;
				qu.push(tmp);
			}
		}
		qu.pop();
	}
	return -1;
}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);

	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'){
				if (vect.size() == 0){
					vect.push_back({ i, j, 0, 0, 0, 0 });
				}
				else{
					vect[0].y2 = i;
					vect[0].x2 = j;
				}
			}
		}
	}

	cout << bfs() << endl;

}