이번 문제는 백준의 골드 4 주사위 굴리기 문제이다.
차근차근 문제를 읽어보자.
지도가 주어지고, 명령이 주어졌을 때 주사위를 명령대로 굴리는 문제이다.
보아하니 주사위의 동작을 직접 구현해야하는 문제인 것 같다.
K개의 명령을 1, 2, 3, 4와 같이 입력받게 되는데,
보통 BFS를 할 때, 우리가 dx, dy 배열을 만들어 이동시키곤 한다.
그 방식대로 1, 2, 3, 4 칸에 각 이동 방향을 할당하여 구현하면 될 것 같다.
또한, 칸을 넘어가면 어떤 명령도 실행하지 않아야 하니 분기로 해결하면 된다.
그러나 가장 큰 문제는 주사위를 어떻게 관리할 것인가? 이다.
주사위를 굴리고 윗면 아랫면을 계속 추적하려면 어떤 자료구조가 필요하다.
도대체 어떤 자료구조를 통해서 유지해야 추적이 가능할까?
이 문제의 핵심인 것 같다.
구현은 정직하게
여러 방면으로 고민해보다, 그냥 배열에 담아서 값만 바꾸어 구현해보기로 했다.
7칸짜리 배열을 만들어, 1 ~ 6번 인덱스에 해당하는 칸을 주사위 면으로 본다.
1번은 윗면, 6번을 아랫면, 2 3 4 5번은 북 동 서 남을 가정하고 구현했다.
사실 어떻게 두든지 굴렸을 때, 면만 안 섞이게 잘 할당하면 될 것 같다.
주사위를 만약 동쪽으로 굴린다면 주사위의 면은 어떻게 될까?
- 1번 자리에 4번 면이 온다. (서쪽면 -> 윗면)
- 3번 자리에 1번 면이 온다. (윗면 -> 동쪽면)
- 6번 자리에 3번 면이 온다. (동쪽면 -> 아랫면)
- 4번 자리에 6번 면이 온다. (아랫면 -> 서쪽면)
위와 같이 주사위를 굴릴 때 마다, 4칸의 값만 바꾸어주면 된다. 그 결과, 아래와 같은 코드가 나오게 된다.
void roll_east() {
int d_top, d_north, d_east, d_west, d_south, d_bottom;
d_top = virtual_dice[1], d_north = virtual_dice[2], d_east = virtual_dice[3];
d_west = virtual_dice[4], d_south = virtual_dice[5], d_bottom = virtual_dice[6];
virtual_dice[1] = d_west;
virtual_dice[4] = d_bottom;
virtual_dice[6] = d_east;
virtual_dice[3] = d_top;
}
void roll_west() {
int d_top, d_north, d_east, d_west, d_south, d_bottom;
d_top = virtual_dice[1], d_north = virtual_dice[2], d_east = virtual_dice[3];
d_west = virtual_dice[4], d_south = virtual_dice[5], d_bottom = virtual_dice[6];
virtual_dice[4] = d_top;
virtual_dice[6] = d_west;
virtual_dice[3] = d_bottom;
virtual_dice[1] = d_east;
}
void roll_south() {
int d_top, d_north, d_east, d_west, d_south, d_bottom;
d_top = virtual_dice[1], d_north = virtual_dice[2], d_east = virtual_dice[3];
d_west = virtual_dice[4], d_south = virtual_dice[5], d_bottom = virtual_dice[6];
virtual_dice[1] = d_south;
virtual_dice[2] = d_top;
virtual_dice[6] = d_north;
virtual_dice[5] = d_bottom;
}
void roll_north() {
int d_top, d_north, d_east, d_west, d_south, d_bottom;
d_top = virtual_dice[1], d_north = virtual_dice[2], d_east = virtual_dice[3];
d_west = virtual_dice[4], d_south = virtual_dice[5], d_bottom = virtual_dice[6];
virtual_dice[5] = d_top;
virtual_dice[1] = d_north;
virtual_dice[2] = d_bottom;
virtual_dice[6] = d_south;
}이제 주사위를 어떻게 굴릴지 구현했으니, 움직이면 된다.
본 구현 코드는 아래와 같다.
void simulate() {
int curr_x = st_x;
int curr_y = st_y;
for (int i = 0; i < cmds; i++) {
int nx = curr_x + dx[cmd_list[i] - 1];
int ny = curr_y + dy[cmd_list[i] - 1];
if ((nx >= 0 && nx < row) && (ny >= 0 && ny < col)) {
roll_dice(cmd_list[i]);
// 주사위도 굴려야 함
if (roads[nx][ny] == 0)
// 0이면 주사위의 아랫면이 칸에 복사된다.
roads[nx][ny] = virtual_dice[6];
else {
// 0이 아니면 칸의 수가 주사위의 밑면에 복사된다.
virtual_dice[6] = roads[nx][ny];
roads[nx][ny] = 0;
}
cout << virtual_dice[1] << '\n';
// 윗면 출력
curr_x = nx;
curr_y = ny;
// 현재 위치를 바꿔줘야 함
}
}
}구현 문제를 풀다보면, 구현하기 까다로운 부분들이 가끔 나온다.
창의적인 아이디어를 생각해내는 것도 좋지만, 가끔은 정직하게 해보자.