[백준] 25208번 새벽의 탐정 게임 [C++]

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

25208번: 새벽의 탐정 게임

---

 

문제

---

문제 요약

문제가 너무 김에 따라서 요약을 하자면,

위와 같은 판에 도둑, 탐정 두가지가 있는데, 탐정은 상하좌우 4가지 방향 중 한곳으로 움직일 수 있다.

탐정은 위의 전개도로 만들어지는 감옥을 본인 시작 지점에서 바닥이 뚫린 채로 시작하며, 움직이는 방향에 따라서 주사위처럼 비어있는 부분또한 움직이게 된다.

 

도둑을 가두기 위해서는 도둑이 있는 지점에 감옥의 바닥이 뚫린 채로 도착을 해야 하며, 바닥이 뚫리지 않은 채로 도둑에게 도착하게 된다면 도둑의 승리가 된다.

 

---

접근 방식

임의로 번호를 지정한 주사위

 

위와 같이 만약 주사위의 상태가 N일경우, N번이라고 적혀있는 면이 뚫려있는 주사위가 있다고 가정해보자.

현재 상태가 0이고, 이동방향이 왼쪽이면 주사위를 왼쪽으로 굴린 후 뚫린부분은 2번이 된다.

이에 따라서 주사위의 상태가 2가된다.

반대로, 현재 상태가 0이고 이동방향이 위쪽이라면 주사위를 위로 굴리게 된다.

그러면 주사위의 상태가 5가 된다.

이런 식으로 현재 상태, 이동 방향에 따라서 다음 주사위의 상태를 정해주는 함수를 만들 필요가 있다.

그 후에, 시작 지점에서 부터 BFS를 해가며 각 지점에 도착했을 떄에 주사위의 상태,지점의 X,Y좌표 등을 기록해둔다.

도착 지점이 도둑이 있는 지점이고, 주사위의 상태가 0이면 도둑을 잡은 것이고, 모든 탐색을 했는데 이러한 도착이 없다면 도둑을 잡지 못 했기 때문에 -1을 출력해준다.

 

주의점

도둑이 있는 지점에 주사위의 상태가 0이 아니라면, 이 상태는 탐색이 되지 않는 상태이다. 0이 아닌 상태에서 도둑이 있는 지점에 가게 될 경우 즉시 패배가 된다. 이 부분을 예외로 꼭 처리해야 한다.

---

코드

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<tuple>
using namespace std;
int dx[4] = { 1,-1,0,0 }; 
int dy[4] = { 0,0,-1,1 }; //아래,위,왼,오
int counter[501][501][6];
int n, m;
char arr[501][501];
int d[2];
int r[2];
bool flag[501][501][6];
int diceState(int dir, int state) { //현재 감옥 위치와,방향에 따라서 바뀌는 감옥 위치를 구하는 함수
	if (dir==0) {
		if (state == 0)return 4;
		if (state == 1)return 5;
		if (state == 2)return 2;
		if (state == 3)return 3;
		if (state == 4)return 1;
		if (state == 5)return 0;
	}
	if (dir == 1) {
		if (state == 0)return 5;
		if (state == 1)return 4;
		if (state == 2)return 2;
		if (state == 3)return 3;
		if (state == 4)return 0;
		if (state == 5)return 1;
	}
	if (dir == 2) {
		if (state == 0)return 2;
		if (state == 1)return 3;
		if (state == 2)return 1;
		if (state == 3)return 0;
		if (state == 4)return 4;
		if (state == 5)return 5;
	}
	if (dir == 3) {
		if (state == 0)return 3;
		if (state == 1)return 2;
		if (state == 2)return 0;
		if (state == 3)return 1;
		if (state == 4)return 4;
		if (state == 5)return 5;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') { //시작 시 도둑이 있는 지점
				r[0] = i;
				r[1] = j;
			}
			if (arr[i][j] == 'D') { //시작 시 탐정이 있는 지점
				d[0] = i;
				d[1] = j;
			}
		}
	}
	counter[d[0]][d[1]][0] = 0; //시작 지점에 바닥이 뚫린 채로는 0번만에 가기 때문에 초기값 세팅
	flag[d[0]][d[1]][0] = true; //방문 지점 저장
	queue<tuple<int, int, int>> q; //X,Y좌표와 더불어 주사위 상태도 큐에 넣어야 하기 때문에 튜플 사용
	q.push({d[0], d[1], 0});
	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int state = get<2>(q.front());
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x2 = x + dx[i];
			int y2 = y + dy[i];
			int state2 = diceState(i, state);			
			if (x2<1|| y2<1 ||x2>n|| y2>m ||flag[x2][y2][state2]||arr[x2][y2]=='#')continue;
			//탐색이 안 되는 경우
            if (x2 == r[0] && y2 == r[1]) { //도착지점이 도둑과 같은 지점일 때
				if (state2 != 0)continue; //주사위 상태가 0이 아니면 탐색하면 안된다.
				else {
					cout << counter[x][y][state] + 1; //주사위 상태가 0이라면,도둑을 잡았기 때문에 정답 출력 후 종료
					return 0;
				}
			}
			else {
				flag[x2][y2][state2] = true;
				counter[x2][y2][state2] = counter[x][y][state] + 1;
				q.push({ x2,y2,state2 });
			}
		}
	}
    //While문이 끝났다는것은 모든 지점을 탐색해도, 도둑을 잡지 못했다는 뜻이다.
	cout << -1; 
}

---

간단한 BFS와 꽤 생각이 필요한 구현을 이요한 문제였다.

---

 

이 문제 까지 IUPC 대회 총 10문제중에서 너무 기초 문제라서 포스팅하지 않은 2개를 제외하고, 내가 해결한 4문제를 모두 포스팅 하였다.

이 문제가 내가 해결했던 문제중에 가장 난이도가 높았고, 실제로 백준 티어측정도 해결한 문제중에서 가장 높게 되었다.

대회 당시에 해결하지 못한 4문제도 답을 보지 않고 최대한 빨리 해결해서 포스팅을 할 것이다.