23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

문제

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다.

  2
4 1 3
  5
  6

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다. 가장 처음에 주사위의 이동 방향은 동쪽이다. 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.

  1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
  2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
  3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
    • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
    • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
    • A = B인 경우 이동 방향에 변화는 없다.

칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다. (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

이 문제의 예제 1부터 7은 같은 지도에서 이동하는 횟수만 증가시키는 방식으로 구성되어 있다. 예제 8은 같은 지도에서 이동하는 횟수를 매우 크게 만들었다.

입력

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다. 

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다.

출력

첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다.

예제 입력 1

4 5 1
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 1

4

가장 처음에 주사위의 이동 방향은 동쪽이다. 따라서, 첫 이동에서 주사위는 (1, 1)에서 (1, 2)로 이동한다. 주사위가 오른쪽으로 한 칸 굴러가고 주사위의 전개도는 다음과 같이 변한다.

  2
6 4 1
  5
  3

(1, 2)에는 1이 있고, (1, 1)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸은 총 4개이다. 따라서, 4점을 획득한다.

주사위의 아랫면에는 3이 있고, (1, 2)에는 1이 있다. 아랫면에 있는 수가 더 크기 때문에, 이동 방향을 90도 시계 방향으로 회전시켜 남쪽이 된다.

예제 입력 2

4 5 2
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 2

8

주사위의 이동 방향은 남쪽이기 때문에, 주사위는 (1, 2)에서 (2, 2)로 이동한다. (2, 2)에서 획득하는 점수도 4점이기 때문에, 현재까지 획득한 점수의 합은 8점이 된다. 주사위의 전개도는 다음과 같아진다.

  3
6 2 1
  4
  5

주사위의 아랫면에는 5가 있고, (2, 2)에는 1이 있다. 아랫면에 있는 수가 더 크기 때문에, 이동 방향은 90도 시계 방향으로 회전된 서쪽이 된다.

예제 입력 3

4 5 3
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 3

14

주사위는 서쪽으로 이동해 (2, 2)에서 (2, 1)로 이동한다. (2, 1)에서 획득하는 점수는 6점이다. 그 이유는 (2, 1)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸이 (2, 1) 하나 밖에 없기 때문이다.

(2, 1)에 도착한 이후 주사위의 전개도는 다음과 같다.

  3
2 1 5
  4
  6

주사위의 아랫면과 (2, 1)에 같은 수가 있기 때문에, 이동 방향은 변하지 않는다.

예제 입력 4

4 5 4
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 4

18

현재 이동 방향은 3번째 이동과 같은 서쪽이다. (2, 1)의 서쪽에는 칸이 없다. 따라서, 이동 방향을 동쪽으로 바꾸고 이동한다. (2, 1)의 동쪽에는 (2, 2)가 있기 때문에, (2, 2)로 이동한다. (2, 2)에 대한 점수는 4점이고, 획득한 점수의 합은 18점이 된다.

이동을 마친 후 주사위의 전개도는 다음과 같다.

  3
6 2 1
  4
  5

주사위의 아랫면에는 5, (2, 2)에는 1이 있다. 아랫면에 있는 수가 더 크기 때문에, 이동 방향을 90도 시계 방향으로 회전시킨다. 따라서, 이동 방향이 동쪽에서 90도 시계 방향으로 회전해 남쪽이 된다.

예제 입력 5

4 5 5
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 5

24

(2, 2)에서 남쪽으로 이동하면 (3, 2)로 이동하게 된다. (3, 2)에는 6이 있는데, 여기서 얻을 수 있는 점수는 6점이다.

주사위의 전개도는 다음과 같다.

  5
6 3 1
  2
  4

주사위의 아랫면에 있는 수 4는 (3, 2)에 있는 수 6보다 작다. 이 경우 이동 방향은 90도 반시계 방향으로 회전시켜야 한다. 현재 이동 방향이 남쪽이었기 때문에, 회전시킨 이동 방향은 동쪽이 된다.

예제 입력 6

4 5 6
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 6

28

(3, 2)에서 동쪽으로 한 칸 이동하면 (3, 3)에 도착한다. (3, 3)에서는 4점을 획득한다. 주사위의 전개도는 다음과 같다.

  5
4 6 3
  2
  1

아랫면에 있는 수와 주사위가 있는 칸에 있는 수가 같다. 이동 방향은 변하지 않는다.

예제 입력 7

4 5 7
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 7

43

(3, 3)에서 동쪽으로 한 칸 이동하면 (3, 4)에 도착한다. (3, 4)의 점수는 15이다.

현재까지 획득한 점수의 합은 43점이다. (3, 4)에 도착했을 때 주사위의 전개도는 다음과 같다.

  5
1 4 6
  2
  3

예제 입력 8

4 5 1000
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 8

3901

알고리즘 분류

  • 구현
  • 시뮬레이션
  • DFS
  • BFS

풀이

처음 주사위 상태

처음 주사위 상태는 다음과 같다. 윗면이 1, 뒷면이 2, 오른쪽 면이 3, 왼쪽 면이 4, 앞면이 5, 아랫면이 6이다.

그리고 처음 위치는 (1, 1), 이동할 방향은 동쪽(동: 1, 서: 3, 남: 2, 북: 4)으로 초기값을 설정하고 주사위의 데이터를 구조체로 선언해주었다.

먼저 주사위가 이동하는 방향에 칸이 있다면 그 쪽으로 이동해주면서 주사위의 숫자들을 바꿔주는데, 여기서 동쪽, 서쪽으로 이동한다면 앞뒷면을 제외한 면들이 시계/반시계 방향으로 90도만큼 이동한다. 마찬가지로 남쪽, 북쪽으로 이동한다면 오른쪽 왼쪽면을 제외한 면들이 앞/뒷방향으로 90도만큼 이동한다. 주사위의 숫자들을 이동시킨 후 주사위의 위치를 변경해주었다. 그런데 이동할 방향에 칸이 없다면 주사위의 이동 방향을 반대(ex) 동 -> 서)로 하고 한 칸 이동시킨다.

두 번째로, BFS를 통하여 현재 위치한 칸의 숫자와 동일한 숫자를 가지는 칸을 탐색하여, 탐색한 칸 X 현재 위치한 칸의 숫자만큼을 점수에 더했다.

마지막으로 주사위의 아랫면과 주사위의 현재 칸에 쓰여 있는 숫자를 비교해서 다음 이동할 방향을 정해주었다.

이 과정을 K번만큼 반복하여 더해지는 점수를 출력하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 25
#define INF 1e9

using namespace std;
struct DICE {
	int Top = 1;
	int Bottom = 6;
	int East = 3;
	int West = 4;
	int Front = 5;
	int Back = 2;
	pair<int, int> Pos = make_pair(1, 1);
	int Dir = 1;
};

DICE Dice;
int N, M, K;
int MAP[MAX][MAX];
// 주사위의 이동 방향(동, 남, 서, 북)
int moveY[5] = { 0,0,1,0,-1 };
int moveX[5] = { 0,1,0,-1,0 };
bool visited[MAX][MAX];
int answer = 0;

void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visited[i][j] = false;
		}
	}
}

void East_Moving() {
	int nextY = Dice.Pos.first + moveY[1];
	int nextX = Dice.Pos.second + moveX[1];
	// 동쪽으로 이동 시 앞뒷면을 제외하면 나머지 면이 시계방향으로 이동한다.
	int tmp = Dice.Top;
	Dice.Top = Dice.West;
	Dice.West = Dice.Bottom;
	Dice.Bottom = Dice.East;
	Dice.East = tmp;
	Dice.Pos = make_pair(nextY, nextX);
}

void West_Moving() {
	int nextY = Dice.Pos.first + moveY[3];
	int nextX = Dice.Pos.second + moveX[3];
	// 서쪽으로 이동 시 앞뒷면을 제외하면 나머지 면이 반시계방향으로 이동한다.
	int tmp = Dice.Top;
	Dice.Top = Dice.East;
	Dice.East = Dice.Bottom;
	Dice.Bottom = Dice.West;
	Dice.West = tmp;
	Dice.Pos = make_pair(nextY, nextX);
}

void South_Moving() {
	int nextY = Dice.Pos.first + moveY[2];
	int nextX = Dice.Pos.second + moveX[2];
	// 남쪽으로 이동 시 양 옆면을 제외하면 나머지 면이 남쪽으로 이동한다.
	int tmp = Dice.Top;
	Dice.Top = Dice.Back;
	Dice.Back = Dice.Bottom;
	Dice.Bottom = Dice.Front;
	Dice.Front = tmp;
	Dice.Pos = make_pair(nextY, nextX);
}

void North_Moving() {
	int nextY = Dice.Pos.first + moveY[4];
	int nextX = Dice.Pos.second + moveX[4];
	// 북쪽으로 이동 시 양 옆면을 제외하면 나머지 면이 북쪽으로 이동한다.
	int tmp = Dice.Top;
	Dice.Top = Dice.Front;
	Dice.Front = Dice.Bottom;
	Dice.Bottom = Dice.Back;
	Dice.Back = tmp;
	Dice.Pos = make_pair(nextY, nextX);
}

int Score_Calc() {
	init();
	int B = MAP[Dice.Pos.first][Dice.Pos.second];
	int C = 1;
	queue<pair<int, int> > Q;
	Q.push(make_pair(Dice.Pos.first, Dice.Pos.second));
	visited[Dice.Pos.first][Dice.Pos.second] = true;

	while (!Q.empty()) {
		int CurY = Q.front().first;
		int CurX = Q.front().second;
		Q.pop();

		for (int i = 1; i <= 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M) && (!visited[nextY][nextX]) && (MAP[nextY][nextX] == B)) {
				visited[nextY][nextX] = true;
				C++;
				Q.push(make_pair(nextY, nextX));
			}
		}
	};
	return (B * C);
}

void Dir_Setting() {
	int A = Dice.Bottom;
	int B = MAP[Dice.Pos.first][Dice.Pos.second];
	if (A > B) {
		Dice.Dir++;
		if (Dice.Dir == 5) {
			Dice.Dir = 1;
		}
	}
	else if (A < B) {
		Dice.Dir--;
		if (Dice.Dir == 0) {
			Dice.Dir = 4;
		}
	}
}

int main() {
	FIRST
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
		}
	}
	for (int i = 0; i < K; i++) {
		int nextY = Dice.Pos.first + moveY[Dice.Dir];
		int nextX = Dice.Pos.second + moveX[Dice.Dir];
		// 1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
		if (Dice.Dir == 1) {
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M)) {
				East_Moving();
			}
			else {
				Dice.Dir = 3;
				West_Moving();
			}
		}
		else if (Dice.Dir == 2) {
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M)) {
				South_Moving();
			}
			else {
				Dice.Dir = 4;
				North_Moving();
			}
		}
		else if (Dice.Dir == 3) {
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M)) {
				West_Moving();
			}
			else {
				Dice.Dir = 1;
				East_Moving();
			}
		}
		else if (Dice.Dir == 4) {
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M)) {
				North_Moving();
			}
			else {
				Dice.Dir = 2;
				South_Moving();
			}
		}
		// 2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
		answer += Score_Calc();
		// 3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
		Dir_Setting();
	}
	cout << answer << "\n";

	return 0;
}

'BOJ > Gold' 카테고리의 다른 글

[BOJ/Gold 3] 백준 1111 IQ Test(C++)  (0) 2022.01.16
[BOJ/Gold 4] 백준 16722 결! 합!(C++)  (0) 2022.01.16
[BOJ/Gold 3] 백준 20327 배열 돌리기 6(C++)  (0) 2022.01.14
[BOJ/Gold 3] 백준 18808 스티커 붙이기(C++)  (0) 2022.01.13
[BOJ/Gold 3] 백준 17822 원판 돌리기(C++)  (0) 2022.01.13

티스토리툴바