백준 25208 - 새벽의 탐정 게임(C++)

문제 링크입니다. https://www.acmicpc.net/problem/25208

25208번: 새벽의 탐정 게임

주사위 굴러가는 방향을 신경써주면 풀 수 있는 문제였습니다.

문제에서 생각해야할 점이 있었습니다.
1. 같은 좌표에 방문하더라도 다른 주사위 방향이라면 다른 방향이다.
2. 주사위가 상하좌우 움직였을 때 어떤 방향으로 움직이는가?

이 두가지를 해결할 수 있으면 풀 수 있는 문제입니다.

먼저 1번을 생각해보겠습니다.
윗면에서 (X, Y)를 방문한 것과 아랫면에서 해당 좌표를 방문한 것은 다른 경우입니다.
따라서 Check 배열을 3차원으로 만들어야 합니다.
3차원 배열을 통해서 [X][Y][현재 주사위 면] 의 방식으로 다른 주사위 면이 왔을 경우 다른 경우로 처리해주면 됩니다.

2번에 대해서 생각해보겠습니다.
예를 들어 현재 주사위가 아랫면입니다. 이때 오른쪽으로 움직이면 왼쪽면으로 바뀝니다. 이와 같이 모든 경우를 확인해주면 됩니다.



자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;

int N, M;
char map[501][501]; // D -> 탐정 // R -> 도둑
int check[501][501][6];
int dx[4] = { 0,1,0,-1 }; // 아래, 오른, 위, 왼
int dy[4] = { 1,0,-1,0 };
pair<int, int> start, finish;
typedef struct qu {
	int x;
	int y;
	int cnt;
	int Dice;
}qu;

int move_dice(int x, int way) {
	// 0 -> 밑면 , 1 -> 오른쪽면 , 2 -> 윗면 , 3 -> 왼쪽면 , 4 -> 뒷면 , 5 -> 앞면
	if (way == 0) {
		if (x == 0) return 4;
		else if (x == 1) return 1;
		else if (x == 2) return 5;
		else if (x == 3) return 3;
		else if (x == 4) return 2;
		else return 0;
	}
	else if (way == 1) {
		if (x == 0) return 3;
		else if (x == 1) return 0;
		else if (x == 2) return 1;
		else if (x == 3) return 2;
		else if (x == 4) return 4;
		else return 5;
	}
	else if (way == 2) {
		if (x == 0) return 5;
		else if (x == 1) return 1;
		else if (x == 2) return 4;
		else if (x == 3) return 3;
		else if (x == 4) return 0;
		else return 2;
	}
	else if (way == 3) {
		if (x == 0) return 1;
		else if (x == 1) return 2;
		else if (x == 2) return 3;
		else if (x == 3) return 0;
		else if (x == 4) return 4;
		else return 5;
	}
}

void find_theif() {
	queue<qu> q;
	q.push({ start.first,start.second,0,0 });
	check[start.first][start.second][0] = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		int Dice = q.front().Dice;
		//cout << x << " " << y << " " << Dice << "\n";
		q.pop();
		if (finish.first == x && finish.second == y) {
			cout << cnt;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			int next_dice = move_dice(Dice, i);
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (finish.first == xx && finish.second == yy && next_dice != 0) continue;
				if (check[xx][yy][next_dice] == 0 && map[xx][yy] != '#') {
					check[xx][yy][next_dice] = 1;
					q.push({ xx,yy,cnt + 1, next_dice });
				}
			}
		}
	}
	cout << "-1";
}

void solve() {
	find_theif();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'D') start = { i,j };
			else if (map[i][j] == 'R') finish = { i,j };
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글 남겨주세요