[백준 C++] 23288 주사위 굴리기 2

문제

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다.

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다. 가장 처음에 주사위의 이동 방향은 동쪽이다. 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.

주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
A = B인 경우 이동 방향에 변화는 없다.
칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다. (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

이 문제의 예제 1부터 7은 같은 지도에서 이동하는 횟수만 증가시키는 방식으로 구성되어 있다. 예제 8은 같은 지도에서 이동하는 횟수를 매우 크게 만들었다.

입력

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다.

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다.

출력

첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다.

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

풀이

1. 주사위가 굴려가며 각 면의 숫자를 구현해야 한다.
   주사위가 동남서북순서대로 굴려갈때 모든면이 바뀌는과정을 일일이 지정해주었다.
   여기서 0, 1, 2, 3으로 방향변수가 증가하는데
   이를 쉽게 계산하기위해서
   
   이와 같이 4 로나뉜 나머지로 0~3을 순환하게 지정했다.
   
   !!! 이때 필자의경우 이와같이 값이 음수가될수도 있도록 나머지연산을 사용했는데 이러면 연산이 복잡해짐에따라 값이 음수가 나오는 오류가 발생한다.
   항상 양수값을 가지도록 지정해주어야한다. !!!
2. 주어진 지도에서 bfs로 숫자가같은칸이 몇칸 인접한지 체크해야한다.
   크게 주의 할점은 없다.

방향변수를 0~3 으로 순환하도록 나머지연산을 사용할때,
음수값을 나머지연산하지 않도록 주의해야겠다..

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::queue; using std::pair;
typedef pair<int, int> pii;
int n, m, k;
int sum = 0; //총점수. 출력값
int** map;
bool** visited;
int top=1, right=3, bottom=6, left=4, backward=5, toward=2;
queue<pii> q;
int dx[] = {0, 1, 0, -1}; //주사위 방향
int dy[] = {1, 0, -1, 0};

void init();
void reset();
int calculate(int current_x, int current_y);
void play();
void roll(int dir);

//0:동 1:남 2:서 3:북
void roll(int dir) { //주사위를 굴리고 바닥면의 숫자를 리턴함
    int _;
    switch (dir) {
    case 0:
        _ = left;
        left = bottom;
        bottom = right;
        right = top;
        top = _;
        break;
    case 1:
        _ = toward;
        toward = bottom;
        bottom = backward;
        backward = top;
        top = _;
        break;
    case 2:
        _ = top;
        top = right;
        right = bottom;
        bottom = left;
        left = _;
        break;
    case 3:
        _ = top;
        top = backward;
        backward = bottom;
        bottom = toward;
        toward = _;
        break;
    }
}

void play() {
    int dir = 0; //0:동 1:남 2:서 3:북
    int current_x = 0, current_y = 0;
    while (k--) {
        //1. 현재 주사위 위치 갱신
        if (current_x + dx[dir] < 0 || current_y + dy[dir] < 0 ||
            current_x + dx[dir] == n || current_y + dy[dir] == m) //지도밖으로 벗어나게되는 경우
            dir = (dir + 2) % 4; //주사위 방향을 반대로 바꾸어 진행
        current_x += dx[dir];
        current_y += dy[dir];
        roll(dir);

        //2. 도착칸의 점수 계산
        sum += calculate(current_x, current_y);
        //printf(">> 주사위바닥%d 지도숫자%d\n", bottom, map[current_x][current_y]);
        if (bottom > map[current_x][current_y])
            dir = (dir + 1) % 4; //시계방향
        if (bottom < map[current_x][current_y])
            dir = (dir - 1) % 4; //반시계

        //printf("  %d\n%d %d %d\n  %d\n  %d\n\n\n", toward, left, top, right, backward, bottom);
    }
    
    printf("%d", sum); //결과 출력
}

//현재위치에서의 총합을 계산
//bfs 로 현재 칸의 수와 같은 값을 가지는 칸의 갯수를 탐색.
int calculate(int current_x, int current_y) {
    int num = map[current_x][current_y]; //현재칸의 값
    int count = 0;
    reset(); //방문배열 초기화
    q.push({ current_x, current_y });
    visited[current_x][current_y] = true;
    count++; //찾은 횟수+1
    while (!q.empty()) {
        int x = q.front().first; //큐에서 좌표를 꺼냄
        int y = q.front().second;
        q.pop();

        //4방향 탐색
        for (int dir = 0; dir < 4; dir++) {
            int xx = x + dx[dir];
            int yy = y + dy[dir];
            if (xx < 0 || yy < 0 || xx == n || yy == m) //잘못된 인덱스 제외
                continue;
            if (visited[xx][yy]) //이미 방문했다면 제외
                continue;
            if (map[xx][yy] != num) //지도의 현재칸과 다른 숫자를 가지면 제외
                continue;

            visited[xx][yy] = true; //탐색 체크
            count++; //찾은 횟수 +1
            q.push({ xx, yy }); //다음 탐색위치로 지정. 큐에 넣음
        }
    }
    return num * count; 
}

void reset() {
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++)
            visited[i][j] = false;
}

void init() {
    scanf("%d%d%d", &n, &m, &k);
    map = new int* [n];
    visited = new bool* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        visited[i] = new bool[m];
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
}

int main(void) {
    init();
    play();

    return 0;
}