백준 23288 주사위 굴리기2

https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

- 단순구현 + DFS/BFS 문제이다. 시간복잡도는 K번의 이동 * 이동 시 BFS하여 O(KMN)

- 이 문제 를 풀어보았다면 무난하게 풀 수 있는 문제이다.

- 가장 먼저, 주사위의 규칙성부터 찾아본다. square 배열을 두고, 초기 값을 {1,2,3,4,5,6}으로 주고 각 4개의 방향으로 이동 시 값이 어떻게 바뀌는지를 캐치해야한다. 초기 상태에서 동쪽을 예로 들면,

4->1
6->4
3->6
1->3

이런식으로 구현을 해야 한다. 이렇게 배열의 값들을 특정 방향으로 한 칸씩 이동하는 알고리즘을 구현 할 때는, 정방향으로 값을 옮기면 원하는대로 값이 이동이 되지 않으므로, 항상 끝 쪽부터 반대로 순환하면서 이동을 시켜야 한다.

예를 들어, {1,2,3,4} => {4,1,2,3}을 만들고 싶은 경우, 즉 오른쪽으로 한 칸씩 이동시키고 싶다면 가장 끝 값인 4는 임시로 저장하고, n=4라 할 때 index가 n-2, 즉 마지막 바로 전 값부터 차례대로 한 칸씩 오른쪽으로 이동한다. 이 후, index 0에 임시로 저장한 4를 넣어주면 된다.

- 처음에는 주어진 방향대로 x,y값을 최신화 한다. 이 때, 주어진 영역을 벗어나는, '벽꿍'을 하는 경우 방향을 반대로 전환해서 최신화한다. 최신화는 현재 방향에 2를 더하고 %4를 해 주면 된다.

- 다음으로 square를 방향에 맞게 최신화한다. 4개의 move_direction 함수로 square를 최신화한다

- 이제 bfs를 진행해서,몇 개의 칸이 연속되었는지를 조사한다. 주의 할 점은 bfs 한 번 진행 할 때마다 visited를 초기화 해 주어야 한다는 점이다. 왜냐하면 다음 bfs때 다시 이 구역을 계산할 수 있기 때문이다. bfs는 총 방문한 칸을 return한다.

- 방문한 칸 * 현재 칸의 정수를 통해 획득한 값을 answer에 추가한다.

- 마지막으로, 다음 방향을 정한다. square의 밑부분의 값과 현재 map의 값을 기반으로 구하면 된다.

- 문제풀이는 50분 정도가 걸렸는데, 처음 아이디어를 떠올리는 데에 시간을 많이 잡아먹었다. 반복 연습만이 답인 듯하다.

#include <iostream> #include <cstring> #include <queue> using namespace std; int n, m, answer; int dx[] = { 0,1,0,-1 }; int dy[] = { 1,0,-1,0 }; int square[] = {1,2,3,4,5,6}; bool visited[20][20]; int now_dir = 0; int map[20][20]; void move_east() { int temp = square[0]; square[0] = square[3]; square[3] = square[5]; square[5] = square[2]; square[2] = temp; } void move_west() { int temp = square[0]; square[0] = square[2]; square[2] = square[5]; square[5] = square[3]; square[3] = temp; } void move_north() { int temp = square[0]; square[0] = square[4]; square[4] = square[5]; square[5] = square[1]; square[1] = temp; } void move_south() { int temp = square[0]; square[0] = square[1]; square[1] = square[5]; square[5] = square[4]; square[4] = temp; } int bfs(int sx, int sy) { visited[sx][sy] = true; queue<pair<int, int>> q; q.push({ sx,sy }); int now_num = map[sx][sy]; int total_num = 1; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue; if (visited[nx][ny] || map[nx][ny] != now_num) continue; visited[nx][ny] = true; q.push({ nx,ny }); total_num++; } } memset(visited, false, sizeof(visited)); return total_num; } int main() { cin >> n >> m; int k; cin >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } int now_x = 0; int now_y = 0; while (k--) { now_x += dx[now_dir]; now_y += dy[now_dir]; if (now_x < 0 || now_x >= n || now_y < 0 || now_y >= m) { now_x -= dx[now_dir]; now_y -= dy[now_dir]; now_dir = (now_dir + 2) % 4; now_x += dx[now_dir]; now_y += dy[now_dir]; } if (now_dir == 0) move_east(); else if (now_dir == 1) move_south(); else if (now_dir == 2) move_west(); else move_north(); int count = bfs(now_x, now_y); answer += (count * map[now_x][now_y]); if (square[5] > map[now_x][now_y]) now_dir = (now_dir + 1) % 4; else if (square[5] < map[now_x][now_y]) now_dir = (now_dir+3) % 4; } cout << answer; }