[오답노트] 주사위 굴리기(BOJ 14499)
Algorithm
September 27, 2023
문제
https://www.acmicpc.net/problem/14499
문제 이해
크게 두 가지 동작으로 요약할 수 있다.
- 주사위를 굴리는 동작
- 주사위를 굴린 후, 지도에 적혀있는 숫자에 따라서 수를 복사하는 동작
즉, 1.을 위해서, 주사위가 동, 서, 북, 남으로 이동할 때의 동작을 구현하고, 2.를 위해서, 주사위를 굴려, 위치를 이동하고 해당 위치에서 지도의 숫자를 확인하여 문제의 동작을 수행하여야 한다.
풀이
주의할 점은 주사위를 굴리는 동작은 면을 실제로 굴릴 필요가 없고, 항상 맨 위의 눈이 1이라고 생각하고 각 면의 숫자만 바꾸면 된다.
- 주사위 구조체 (
Dice) - 주사위의 각 면에 적혀있는 수를 저장하는 배열face와, - 현재 주사위의 위치를 (x,y)를 관리한다.
struct Dice {
int face[7]; // 1번 면부터 6번 면까지 적혀있는 숫자
int x;
int y;
};- 주사위 굴리기 (
RollDice) - 앞에 언급했듯이, 주사위의 모양이 항상 고정되어있다고 생각한다. 즉, 문제에 적혀있는 대로 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있다. - 주사위를 움직였을 때, 숫자는 다음과 같이 변한다.
따라서, 예를 들어 동쪽으로 굴렸다고 하면 1번 면에 4번에 쓰여있던 수를 복사하고, 6번 면에 3번에 쓰여있던 수를 복사하는 식으로 주사위를 굴리는 과정을 구현할 수 있다.
이 때, 마주보는 주사위 눈의 합이 7이라는 것을 이용하면 조금 더 편하게 구현 할 수 있다. (예를 들어, 1번 면에 4번 면에 쓰여 있는 수를 업데이트 하면, 6번 면에 2번 면에 쓰여 있는 수로 업데이트 함)
void rollDice(int dir) {
// 원래 눈에 있던 값들
int d1 = dice.face[1];
int d2 = dice.face[2];
int d3 = dice.face[3];
int d4 = dice.face[4];
int d5 = dice.face[5];
int d6 = dice.face[6];
switch (dir) {
case EAST: {
dice.face[1] = d4;
dice.face[6] = d3;
dice.face[4] = d6;
dice.face[3] = d1;
break;
}
case WEST: {
dice.face[1] = d3;
dice.face[6] = d4;
dice.face[4] = d1;
dice.face[3] = d6;
break;
}
case NORTH: {
dice.face[1] = d5;
dice.face[2] = d1;
dice.face[5] = d6;
dice.face[6] = d2;
break;
}
case SOUTH: {
dice.face[1] = d2;
dice.face[2] = d6;
dice.face[5] = d1;
dice.face[6] = d5;
break;
}
}
}주의사항
계속 언급하는 거지만, 면을 계속 옮기지말고 면은 고정되었다고 생각하고 숫자만 바꾸는 형식으로 구현한다!
코드
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define X first
#define Y second
using namespace std;
// 주사위의 맨 위의 면은 항상 1이라고 생각하고, 숫자만 갱신한다!
enum Direction { EAST = 1, WEST, NORTH, SOUTH };
struct Dice {
int face[7]; // 1번 면부터 6번 면까지 적혀있는 숫자
int x;
int y;
};
// 동, 서, 북, 남, 1-indexed
const array<int, 5> DX = {0, 0, 0, -1, 1};
const array<int, 5> DY = {0, 1, -1, 0, 0};
int n, m, x, y, k;
vector<vector<int>> game_map;
Dice dice;
void input() {
FASTIO;
// 테스트를 위한 파일 입력 코드 (TODO: 제출 전 삭제)
// freopen("sample_input.txt", "r", stdin);
cin >> n >> m >> x >> y >> k;
game_map.resize(n, vector<int>(m));
dice.x = x;
dice.y = y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> game_map[i][j];
}
}
}
void rollDice(int dir) {
// 원래 눈에 있던 값들
int d1 = dice.face[1];
int d2 = dice.face[2];
int d3 = dice.face[3];
int d4 = dice.face[4];
int d5 = dice.face[5];
int d6 = dice.face[6];
switch (dir) {
case EAST: {
dice.face[1] = d4;
dice.face[6] = d3;
dice.face[4] = d6;
dice.face[3] = d1;
break;
}
case WEST: {
dice.face[1] = d3;
dice.face[6] = d4;
dice.face[4] = d1;
dice.face[3] = d6;
break;
}
case NORTH: {
dice.face[1] = d5;
dice.face[2] = d1;
dice.face[5] = d6;
dice.face[6] = d2;
break;
}
case SOUTH: {
dice.face[1] = d2;
dice.face[2] = d6;
dice.face[5] = d1;
dice.face[6] = d5;
break;
}
}
}
bool isValidRange(pair<int, int> p) {
return 0 <= p.X && p.X < n && 0 <= p.Y && p.Y < m;
}
void solve() {
for (int op = 0; op < k; op++) {
int cmd;
cin >> cmd;
pair<int, int> next = {dice.x + DX[cmd], dice.y + DY[cmd]};
if (isValidRange(next)) {
rollDice(cmd);
dice.x = next.X;
dice.y = next.Y;
if (game_map[next.X][next.Y] == 0) {
// 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다.
game_map[next.X][next.Y] = dice.face[6];
} else {
// 칸에 쓰여 있는 수가 주사위의 바닥 면에 복사되고,
// 칸에 있는 수는 0이 된다.
dice.face[6] = game_map[next.X][next.Y];
game_map[next.X][next.Y] = 0;
}
cout << dice.face[1] << '\n';
}
}
}
int main() {
input();
solve();
return 0;
}