백준 14499. 주사위 굴리기
구현 및 시뮬레이션 문제
주사위 시뮬레이션을 다루는 방법
문제 분석
주사위 굴리기
- N * M 인 지도가 주어짐
- 오른쪽은 동쪽, 위쪽은 북쪽
- 주사위 하나가 주어짐. 주사위의 전개도는 다음과 같다
- 주사위는 지도 위에 윗면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져있으며, 놓여져 있는 곳의 좌표는 (y,x)다
- 가장 처음에 주사위에는 모든 면에 0이 적혀있다
1 2 3 4
2 4 1 3 5 6
- 지도 각 칸에 정수가 하나씩 쓰여져있다
- 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이면, 주사위 바닥면에 쓰여져 있는 수가 칸에 복사된다.
- 0이 아닌 경우에는, 칸에 쓰여있는 수가 주사위 바닥면으로 복사되며, 칸에 쓰여있는 수는 0이 된다
- 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때 마다, 상단에 쓰여있는 값을 구하는 프로그램을 작성하기
- 주사위는 지도 바깥으로 이동할 수 없으며, 해동 명령을 수행하려는 경우, 출력값 없음
입력
- 첫째 줄에 세로크기 M, 가로크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다
- 줄째 줄 부터 N개의 줄에 지도에 쓰여있는 수가 북쪽으로부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다.
- 주사위를 놓은 칸에 쓰여있는 수는 항상 0임
- 지도의 각 칸에 쓰여있는 수는 10 미만의 자연수 또는 0
- 마지막 줄에는 이동하면 명령이 순서대로 주어진다. 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4
출력
이동할 때마다 주사위의 윗 면에 쓰여있는 수를 출력한다. 만약 바깥으로 이동시키려 하는 경우, 해당 명령을 무시해야하며, 출력도 하면 안된다
예제 분석
1)
1
2
3
4
5
6
4 2 0 0 8
0 2
3 4
5 6
7 8
4 4 4 1 3 3 3 2
4x2 지도의 (0,0)에서 시작, 총 8번 굴린다
지도와 주사위의 초기값은 다음과 같다
1
2
3
4
5
지도
0 2
3 4
5 6
7 8
주사위를 {윗면, 북, 동, 서, 남, 아랫면} 순서로 기록한다면
현재는 {0,0,0,0,0,0}이다. 시작시 1이 윗면, 3이 오른쪽인 상태이다
1
2
3
4
5
6
7
8
9
4 : 남쪽으로 이동. 5가 (1,0)의 3과 닿음. 3이 복사되어 5에 들어감
지도 주사위
0 2 0
0 4 0 0 0
5 6 3
7 8 0
주사위 : {0,0,0,0,3,0}
윗면(2)를 출력 : 0
1
2
3
4
5
6
7
8
9
4 : 남쪽으로 이동. 1이 (2,0)과 닿음. 5가 복사되어 1에 들어감
지도 주사위
0 2 0
0 4 0 5 0
0 6 3
7 8 0
주사위 : {5,0,0,0,3,0}
윗면(6)을 출력 : 0
…
이런식으로 주사위를 시뮬레이션 하면서 풀어본다. 직접 그려가면서 회전했을때 어떤 모양이 되는지 체크하는게 편함
알고리즘
예제를 따라가다보면 주사위의 상태를 잘 체크하는게 매우 중요해보인다
일단 주사위의 각 면의 숫자를 기록할 배열
dice[6] = {윗면,북쪽,동쪽,서쪽,남쪽,아랫면}를 두고, 다음 이동시에 이 값들이 어떻게 이동하는지 추적해본다
동쪽으로 굴리면 : dice_next[6] = {서, 북, 위, 아래, 남, 동}
서쪽으로 굴리면 : dice_next[6] = {동, 북, 아래, 위, 남, 서}
북쪽으로 굴리면 : dice_next[6] = {남, 위, 동, 서, 아래, 북}
남쪽으로 굴리면 : dice_next[6] = {북, 아래, 동, 서, 위, 남}
이런식으로 저장된다
이동한 다음에는 해당 칸이 0인지 아닌지 여부에 따라 행동이 결정된다
이동 불가능하다면 출력도, 동작도 수행하지 않는다
0 인 경우 : 주사위의 바닥 면에 쓰여있는 수가 칸에 “복사” 된다.
복사라고 했으므로, 주사위의 값은 0이 되지 않으므로 주의
0이 아닌 경우 : 칸에 쓰여진 수가 주사위 바닥면으로 복사되며, 칸의 쓰여있는 수는 0이 된다
여기서는 맵에 기록된 값이 0으로 바뀐다고 했으므로 주의
1
2
3
4
5
6
7
1. 전처리
- N, M과 (x, y), 그리고 K를 입력받는다
- 지도를 입력받는다
2. K번 명령을 입력받으면서, 규칙을 수행한다
2-1. 굴릴 방향 입력받기
2-2. 주사위 굴리기, 맵 교환
2-3. 성공적으로 수행했다면 현재 윗면의 숫자를 출력
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstring>
using namespace std;
int N, M;
int map[21][21];
int y, x;
int K;
int dice[6] = { 0 }; // {윗면, 북, 동, 서, 남, 아랫면} 순서
bool print_flag;
void roll_east() {
// 주사위 현재 좌표 갱신
int dx = x + 1;
if (dx >= M) return; // 맵 밖으로 못나감
x = dx;
print_flag = true;
// 주사위의 면 정보 갱신
// dice_next[6] = { 서, 북, 위, 아래, 남, 동 }
int dice_next[6] = { 0 };
dice_next[0] = dice[3];
dice_next[1] = dice[1];
dice_next[2] = dice[0];
dice_next[3] = dice[5];
dice_next[4] = dice[4];
dice_next[5] = dice[2];
memcpy(dice ,dice_next, sizeof(dice));
}
void roll_west() {
int dx = x - 1;
if (dx < 0) return;
x = dx;
print_flag = true;
// dice_next[6] = {동, 북, 아래, 위, 남, 서}
int dice_next[6] = { 0 };
dice_next[0] = dice[2];
dice_next[1] = dice[1];
dice_next[2] = dice[5];
dice_next[3] = dice[0];
dice_next[4] = dice[4];
dice_next[5] = dice[3];
memcpy(dice, dice_next, sizeof(dice));
}
void roll_north() {
int dy = y - 1;
if (dy < 0) return;
y = dy;
print_flag = true;
// dice_next[6] = { 남, 위, 동, 서, 아래, 북 }
int dice_next[6] = { 0 };
dice_next[0] = dice[4];
dice_next[1] = dice[0];
dice_next[2] = dice[2];
dice_next[3] = dice[3];
dice_next[4] = dice[5];
dice_next[5] = dice[1];
memcpy(dice, dice_next, sizeof(dice));
}
void roll_south() {
int dy = y + 1;
if (dy >= N) return;
y = dy;
print_flag = true;
// dice_next[6] = { 북, 아래, 동, 서, 위, 남 }
int dice_next[6] = { 0 };
dice_next[0] = dice[1];
dice_next[1] = dice[5];
dice_next[2] = dice[2];
dice_next[3] = dice[3];
dice_next[4] = dice[0];
dice_next[5] = dice[4];
memcpy(dice, dice_next, sizeof(dice));
}
void CheckMap(int cur_y, int cur_x) {
// 이동한 칸의 수가 0이면, 주사위 바닥면의 숫자를 복사
if (map[cur_y][cur_x] == 0) {
map[cur_y][cur_x] = dice[5];
}
// 0이 아니라면, 주사위 바닥면에 복사한 뒤, 칸에 쓰여있는 숫자를 0으로 바꿈
else {
dice[5] = map[cur_y][cur_x];
map[cur_y][cur_x] = 0;
}
cout << dice[0] << '\n';
}
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M >> y >> x >> K;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
cin >> map[y][x];
}
}
for (int i = 0; i < K; i++) {
int cmd; cin >> cmd;
print_flag = false;
if (cmd == 1) {
roll_east();
}
else if (cmd == 2) {
roll_west();
}
else if (cmd == 3) {
roll_north();
}
else if (cmd == 4) {
roll_south();
}
// 주사위 굴리고 나서 맵과 상호작용
if(print_flag)
CheckMap(y, x);
}
return 0;
}
삼성 문제 답게 구현에 충실했는지를 묻는 문제였다
주사위 시뮬레이션은 이번에 처음 다뤄봤는데, 다음 이동시에 어떻게 될지를 추적하는게 관건이였다
처음 접근은, 윗면과 우측면만 추적하고 규칙을 찾아보려 했으나 실패
힌트를 참조해서 굴렸을때, 이전의 면들이 다음 굴렸을 때 어디로 가는지를 추적하는 방식으로 풀이할 수 있었다
그리고, 이동 실패 시 해당 명령을 무시하고, 출력도 무시하는 부분도 은근 까다로워서 구조가 조금 더러워진것 같다
좋은문제