https://www.acmicpc.net/problem/14499
주사위의 초기 위치와 이를 이동시키는 명령이 주어질 때, 주사위가 이동할 때마다 상단에 쓰여있는 숫자를 출력하는 프로그램을 작성하시오.
문제에 주어진대로 그림을 그려보며 예제의 답이 어떻게 나온건지 생각해보자.
주사위의 전개도에 따라 위와 같이 서로 마주 보는 면끼리 색상을 같게 칠해보았다. 그리고 문제에 주어진 명령어대로 주사위를 굴리면서 <> 괄호 안에 주사위 윗면에 적힌 숫자가 무엇인지 적었다.
위와 같은 과정을 통해 대략 알고리즘을 정리해보면 다음과 같다.
- 동서남북 중 한 방향으로 주사위를 굴린다. (지도를 벗어나는 위치는 제외)
- 지도 칸에 0이 아닌 숫자가 적혀있으면, 주사위의 바닥면에 숫자를 복사하고 해당 칸은 0으로 바꾼다.
- 지도 칸에 0이 적혀있으면, 주사위 바닥면에 적힌 숫자를 지도 칸에 복사한다.
- 현재 주사위 윗면에 적힌 숫자를 출력한다.
- 다시 1번으로 돌아가서 반복한다. (명령어가 끝날 때까지)
3차원으로 된 주사위를 어떻게 굴려야 할지.... 이 부분에서 아이디어가 도저히!! 떠오르지 않아 다른 사람 풀이를 참고하였다.
위와 같이 주사위의 각 면에 해당하는 숫자를 저장하는 dice 벡터를 하나 만든다. 인덱스 번호를 맞추기 위해 크기를 7로 할당한다.
// 1: 위, 2: 북, 3: 동, 4: 서, 5: 남, 6: 아래
vector<int> dice(7);
초기에 주사위 벡터는 {0, 1, 2, 3, 4, 5, 6} 의 값을 갖게 된다. 이 상태에서 4방향으로 굴렸을 때, 벡터 안의 원소들은 다음과 같이 규칙성 있게 값이 변한다.
주사위 | 위 | 북 | 동 | 서 | 남 | 아래 | 비고 |
---|---|---|---|---|---|---|---|
초기 | 1 | 2 | 3 | 4 | 5 | 6 | |
동쪽 | 4 | 2 | 1 | 6 | 5 | 3 | 남북 그대로, 나머지 회전 |
서쪽 | 3 | 2 | 6 | 1 | 5 | 4 | 남북 그대로, 나머지 회전 |
북쪽 | 5 | 1 | 3 | 4 | 6 | 2 | 동서 그대로, 나머지 회전 |
남쪽 | 2 | 6 | 3 | 4 | 1 | 5 | 동서 그대로, 나머지 회전 |
따라서, 벡터의 원소들 간의 위치만 바꿔주면, 굴릴 때마다 바뀌는 주사위 상태를 구현할 수 있다.
// 동쪽으로 굴리기
void rollEast(){
dice = {0, dice[4], dice[2], dice[1], dice[6], dice[5], dice[3]};
}
// 서쪽으로 굴리기
void rollWest(){
dice = {0, dice[3], dice[2], dice[6], dice[1], dice[5], dice[4]};
}
// 북쪽으로 굴리기
void rollNorth(){
dice = {0, dice[5], dice[1], dice[3], dice[4], dice[6], dice[2]};
}
// 남쪽으로 굴리기
void rollSouth(){
dice = {0, dice[2], dice[6], dice[3], dice[4], dice[1], dice[5]};
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <deque>
using namespace std;
typedef pair<int, int> pii;
const int MAX = 21;
int N, M, K, x, y;
int map[MAX][MAX];
vector<int> cmd;
// 주사위 면: 위 북 동 서 남 아래 (초기에는 모든 면을 0으로 초기화)
vector<int> dice(7, 0);
// 주사위 굴리는 방향: 동서북남
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
void input() {
cin >> N >> M >> x >> y >> K;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> map[i][j];
}
}
for(int i = 0; i < K; i++){
int dir;
cin >> dir;
cmd.push_back(dir - 1);
}
}
void rollEast(){
dice = {0, dice[4], dice[2], dice[1], dice[6], dice[5], dice[3]};
}
void rollWest(){
dice = {0, dice[3], dice[2], dice[6], dice[1], dice[5], dice[4]};
}
void rollNorth(){
dice = {0, dice[5], dice[1], dice[3], dice[4], dice[6], dice[2]};
}
void rollSouth(){
dice = {0, dice[2], dice[6], dice[3], dice[4], dice[1], dice[5]};
}
void rollDice(int direction){
switch(direction){
case 0: rollEast(); break;
case 1: rollWest(); break;
case 2: rollNorth(); break;
case 3: rollSouth(); break;
default: break;
}
}
void solution() {
for(auto dir: cmd){
// 주사위의 다음 위치 계산
int nx = x + dx[dir];
int ny = y + dy[dir];
// 범위 체크
if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
// 명령어에 따라 주사위 굴리기
rollDice(dir);
if(map[nx][ny] == 0){
// 바닥면에 적힌 숫자를 칸에 복사
map[nx][ny] = dice[6];
}else{
// 칸에 적힌 숫자를 주사위 바닥면에 복사
dice[6] = map[nx][ny];
// 칸은 0으로 변경
map[nx][ny] = 0;
}
// 주사위 윗면에 적힌 수 출력
cout << dice[1] << "\n";
// 주사위 위치 갱신
x = nx;
y = ny;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}
시뮬레이션 문제.... 많은 연습이 필요하다!!! 🥹