[백준] 23288번: 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

앞서 풀었던 주사위 문제와 구조 자체는 비슷하다.

그러나 조금 더 살이 덧붙여져서 이 점까지 고려해야 한다.

 

예를 들면 더이상 해당 방향으로 진입이 불가능하면 방향을 뒤집거나, 추가적으로 DFS 혹은 BFS를 써서 탐색을 해서 추가점수를 고려해야 한다.

 

궁극적으로 삼성 SW 역량 테스트를 준비하기 위해 이 문제를 푸는 것이기 때문에, 이에 맞추어 입력을 편하게 받는 방법을 학습했다.

 

필요한 헤더를 include한 후에 #pragma warning(disable:4996)를 포함해주면 input.txt파일을 stdin입력처럼 활용할 수 있다!! 매우 유용! 넘나 유용!!

main 상단에

freopen("input.txt", "r", stdin)

라고 입력만 하면 끝~

 

그런데 주의할 점은 코드 복사 붙여넣기를 할 때 이 코드는 빼고 입력해야한다는 점을 잊지 말아야한다^_____________^

이거 때문에 제출하면 자꾸 틀렸대서 코드 잘못 짠 줄 알고 30분 넘게 헤맸다..ㅠ

 

다시 한 번 언급하지만 주사위의 경우 면이 얼마 되지 않기 때문에(6개) 그냥 면들을 회전시켜버리고 앞면, 뒷면을 고정해두면 필요한 숫자를 추출하기 용이하다.

 

그리고 오랜만에 DFS식으로 간단하게 문제를 적용했는데, 중복 카운트를 방지하기 위해 visited 표기하는 것을 잊지않아야 한다! visited를 true로 설정하는 것은 함수 첫 시작하는 데에 넣어도 되고, 재귀 함수를 호출하는 데에 넣어도 된다. 참고로 BFS의 경우에는 queue를 넣어줄 때 visited를 true로 해줘야 한다. 중복으로 queue에 넣는 것보다 아예 unique하게 넣어주는 것이 메모리상 좋기 때문이다.

#include <iostream>
#include <vector>
//#pragma warning(disable:4996)
using namespace std;
int n, m, k;
int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };
int dice[6] = { 2,1,5,6,4,3 };
vector<vector<int>> arr(21, vector<int>(21));
void roll_dice(int dir) {
    int dice0 = dice[0], dice1 = dice[1], dice2 = dice[2];
    int dice3 = dice[3], dice4 = dice[4], dice5 = dice[5];

    if (dir == 0) {
        dice[4] = dice3;
        dice[3] = dice5;
        dice[5] = dice1;
        dice[1] = dice4;
    }
    else if (dir == 1) {
        dice[0] = dice3;
        dice[1] = dice0;
        dice[2] = dice1;
        dice[3] = dice2;
    }
    else if (dir == 2) {
        dice[4] = dice1;
        dice[1] = dice5;
        dice[5] = dice3;
        dice[3] = dice4;
    }
    else {
        dice[0] = dice1;
        dice[1] = dice2;
        dice[2] = dice3;
        dice[3] = dice0;
    }
}

bool inside(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < m;
}

int dfs(int r, int c, vector<vector<bool>>& visited, vector<vector<int>>& arr, int num) {
    int cnt = 1;
    visited[r][c] = true;
    // cout << "r,c : " << r << " " << c << endl;

    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];

        if (inside(nr, nc) && !visited[nr][nc] && arr[nr][nc] == num) {
            cnt += dfs(nr, nc, visited, arr, num);
        }
    }

    return cnt;

}


void init() {
    //freopen("input.txt", "r", stdin);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
}

int main() {
    int d = 0, r = 0, c = 0;
    int answer = 0;
    init();
    while (k--) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (!inside(nr, nc)) {
            d = (d + 2) % 4;
            nr += dr[d] * 2;
            nc += dc[d] * 2;
            // cout << d << " " << nr << " " << nc << endl;
        }
        roll_dice(d);
        int bottom = dice[3];
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        int cnt = dfs(nr, nc, visited, arr, arr[nr][nc]);

        answer += cnt * arr[nr][nc];
        // cout << cnt << " " << arr[nr][nc] << endl;

        if (bottom > arr[nr][nc]) {
            d = (d + 1) % 4;
        }
        else if (bottom < arr[nr][nc]) {
            d = (d + 3) % 4;
        }
        r = nr;
        c = nc;
    }

    cout << answer << '\n';
}