[알고리즘] DFS/BFS 활용 ④

1. 개요

boj 23288. 주사위 굴리기2

1) 문제 개요

N x M 지도의 (1,1) 위치에 주사위가 놓여있다. 주사위가 동서남북으로 이동하며 얻게되는 점수를 계산한다.

• 주사위의 초기 이동 방향은 '동'쪽이다.
• 주사위는 이동 방향으로 +1칸 쿨러간다. 만약 칸이 없다면(지도 밖의 범위라면) 반대 방향으로 +1칸 이동
• 주사위가 도착한 칸의 점수(B) 획득
• 다음 이동 방향은 주사위의 아랫면의 있는 정수(A)와 지도 위의 정수(B) 를 비교해 결정
  ① A > B 90도 시계 회전
  ② A < B 90도 반시계 회전
  ③ A = B 이동 방향 유지
• 주사위가 도착한 칸의 점수 계산은 다음과 같다.
  (x,y)칸의 점수 = B X C
  B = (x,y)의 지도위 정수
  C = (x,y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수(C), 이때 이동할 수 있는 칸에는 모두 정수(B)가 있어야한다.

※ 여기서 C를 계산 할 때 "연속" 즉, 사방위를 검사하는 것이 아니라 i) 동서남북 방향으로 이동할 수 있는 ii) 값이 B인 모든 칸의 수를 계산하도록 한다.

2) 입출력 예시

2. Solution I.

1) 알고리즘 구조

위 문제 풀이를 위해 다음의 Func을 생각해볼 수 있다.

① 주사위 전개도 갱신 함수
현재의 전개도와 이동 방향(동서남북)이 주어졌을때 주사위를 굴린 후의 전개도를 반환하는 함수

• 주사위를 동쪽으로 굴리면 아래와 같이 전개도가 바뀐다.
  

② 동서남북 연속 탐색 함수
현재의 위치가 주어졌을 때 지도 위 동서남북 연속으로 이동할 수 있는 연속적인 칸의 수(C)를 계산하는 함수

• 아래의 예시에서 지도 위 (1,1)에서 동서 남북으로 연속해 탐색 가능한 칸의 수는 4개이다.
  

#include <iostream>
#include <vector>
using namespace std;
int n, m, k;
vector<vector<int>>mp;
vector < vector<bool>> v;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

// 주사위의 아래,동쪽,남쪽의 값을 저장
vector<int> dice;
int x, y, d;

// (i,j)에서의 C(동서남북 연속 이동 가능 칸의 수) 계산
int getC(int i, int j, int val)
{
    if (i < 0 || i >= n || j < 0 || j >= m || mp[i][j] != val) return 0;
    //cout << "(" << i << "," << j << ")" << endl;
    
    v[i][j] = true;

    int count = 1;
    // 남
    if (i + 1 < n)
        if(!v[i+1][j] && mp[i+1][j]==val)
			count += getC(i + 1, j, val);
    // 북
    if(i-1>=0)
        if(!v[i-1][j] && mp[i-1][j]==val)
			count += getC(i - 1, j, val);
    // 동
    if(j+1<m)
        if(!v[i][j+1] && mp[i][j+1]==val)
			count += getC(i, j+1, val);
    // 서
    if(j-1>=0)
        if(!v[i][j-1] && mp[i][j-1]==val)
			count += getC(i, j-1, val);

    return count;
}
// 0 1 2 3 동남서북
void moveDir(int dir, int type)
{
    // case 1 (90도 시계)
    if (type == 1)
        if (dir == 3) d = 0;
        else d++;
    // case 2 (90도 반시계)
    else
        if (dir == 0)d = 3;
        else d--;
}

// dir방향으로 굴렸을 때 주사위 아랫면의 값을 계산
int getNext(int dir)
{
    // 아래 / 동 / 남
    // 동
    if (dir == 0)
    {
        int tmp = dice[0];
        dice[0] = dice[1];
        dice[1] = (7 - tmp);
    }
    // 남
    else if (dir == 1)
    {
        int tmp = dice[0];
        dice[0] = dice[2];
        dice[2] = (7 - tmp);
    }
    // 서
    else if (dir == 2)
    {
        int tmp = dice[0];
        dice[0] = (7 - dice[1]);
        dice[1] = tmp;
    }
    // 북
    else
    {
        int tmp = dice[0];
        dice[0] = (7 - dice[2]);
        dice[2] = tmp;
    }
    return dice[0];
}

// dir 방향으로 이동, 이동 불가하다면 반대 방향으로 
void getNextPath(int i, int j, int dir)
{
    if (dir == 0)
    {
        if (j + 1 < m)
        {
            y = ++j;
            x = i;
        }
        else
        {
            d = 2;
            getNextPath(i, j, 2);
        }
    }
    if (dir == 1)
    {
        if (i + 1 < n)
        {
            x = ++i;
            y = j;
        }
        else
        {
            d  = 3;
            getNextPath(i, j, 3);
        }
    }
    if (dir == 2)
    {
        if (j - 1 >= 0)
        {
            y = --j;
            x = i;
        }
        else
        {
            d = 0;
            getNextPath(i, j, 0);
        }
    }
    if (dir == 3)
    {
        if (i - 1 >= 0)
        {
            x = --i;
            y = j;
        }
        else
        {
            d = 1;
            getNextPath(i, j, 1);
        }
    }
}


int main()
{
    int res = 0;
    int dir = 0;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    mp = vector<vector<int>>(n, vector<int>(m, 0));
    dice.push_back(6);
    dice.push_back(3);
    dice.push_back(5);

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < m;j++)
        {
            int tmp;
            cin >> tmp;
            mp[i][j] = tmp;
        }
    }
    // (0,0)에서 시작
    x = 0, y = 0, dir = 0;
    // a : 주사위 아랫면 정수
    int a = 6;

    for (int i = 0;i < k;i++)
    {
        // 0. +1칸 전진
        getNextPath(x, y, d);
        a = getNext(d);
        
        cout << "(" << x << "," << y << ") dir: "<< d <<" dice : "<< a << endl;

        // 1. dfs 탐색
        v = vector<vector<bool>>(n, vector<bool>(m, false));
        v[x][y] = true;
        int c = getC(x,y,mp[x][y]);
        int b = mp[x][y];

        // 2. 점수 계산
        res += (b * c);

        // 3. 다음 이동 방향 갱신
        if (a > b) { moveDir(d, 1);}
        else if (a < b) { moveDir(d, 2);}
        else { ; }
    }
    cout << res << endl;
    return 0;
}