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

백준의 주사위굴리기2(23288) 문제이다.

 

[ 문제풀이 ]

주어진 조건에 맞게 주사위를 굴렸을 때, 획득할 수 있는 점수의 총합을 구해야 하는 문제이다.

과정이 몇 가지 되지는 않지만, 이 과정들을 하나하나씩 알아보고 최종적으로 정답을 도출하는 과정까지 진행해보자.

 

#1. 주사위 굴리기

가장 먼저, 주사위를 주어진 이동방향으로 한 칸 굴려야 한다.

만약, 주어진 이동방향으로 움직일 수 없다면, 이동방향을 반대로 바꿔준 후에 굴리면 된다.

특별히 필요한 알고리즘 같은것이 필요한 부분이 아니기에, 소스코드로 대체하겠다.

아래의 코드는 주사위가 (x , y)에 있다고 가정했을 때, (nx , ny)로 굴러가는 과정이다.

int reverseDir(int d) {
	switch (d) {
	case 0:
		return 1;
	case 1:
		return 0;
	case 2:
		return 3;
	case 3:
		return 2;
	}
}

{
  int nx = x + dx[d];
  int ny = y + dy[d];
  if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
    d = reverseDir(d);
    nx = x + dx[d];
  	ny = y + dy[d];
  }
}

 

#2. 점수 획득하기

#1의 과정에서 주사위가 (x , y)에서 (nx , ny)로 왔다면, (nx , ny)에서 얻을 수 있는 점수를 구하는 과정이 필요하다.

점수는, (nx , ny)에서 연속해서 이동할 수 있는 칸들 중에서, (nx , ny)와 같은 값을 가지고 있는 좌표로만 움직일 때, 이동할 수 있는 칸 수와 (nx , ny)가 가지고 있는 값을 곱한 값이다.

본인은 이 과정을 완전탐색으로, 완전탐색 중에서도 너비우선탐색(BFS)을 이용해서 움직일 수 있는 모든 칸수들을 Count해서 계산 해 주었다.

void getScore(int a, int b) {
	memset(visit, false, sizeof(visit));

	int num = map[a][b];
	int cnt = 1;

	queue<pair<int, int>> q;
	q.push(make_pair(a, b));
	visit[a][b] = true;

	while (q.empty() == 0) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
				if (map[nx][ny] == num && visit[nx][ny] == false) {
					visit[nx][ny] = true;
					cnt++;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	answer += (num * cnt);
}

위의 코드에서 'cnt' 라는 변수가 움직일 수 있는 칸 수이다. (nx , ny)또한 1칸으로 계산을 하기 때문에, cnt의 초기값을 1로 설정해준 후, BFS탐색을 하면서 갈 수 있는 좌표들을 모두 Count 해 주었다.

 

#3. 주사위 상태 변환

이 문제에서 구현해줘야 할 가장 마지막 부분이다. 주사위가 한번 굴러갈 때 마다 주사위의 상태를 바꿔주어야 한다.

예를 들어서 가장 초기에는 가장 윗면이 '1'이였지만 오른쪽으로 한번 구르게 되면 초기의 왼쪽면이였던 '4'가 윗면이 되어버리게 된다. 이처럼 주사위의 상태가 바뀌게 된다.

본인은 주사위의 상태를 표시하는 dice[] 라는 1차원 배열을 하나 만들어 주었다.

가장 초기에는, dice[] = { 0, 1, 2, 3, 4, 5, 6 } 이 될 것이다. 0번 Index의 값을 0으로 넣어준 것은, 문제와 똑같이 계산하기 위해서이다. 문제에서 초기 주사위의 상태를 가장 윗면을 '1'로 표현하였는데 마찬가지로 1번을 윗면으로 표현하기 위해서 0번 Index는 그냥 0으로 채워놓고 사용하지 않은 것이다.

 

주사위의 상태를 바꾸는 것은 총 4가지 경우가 있다. 왜냐하면, 주사위가 굴러갈 수 있는 방향이 동/서/남/북 4가지 방향이 있기 때문이다.

동쪽으로 굴러가게 되면, 주사위의 윗면이 오른쪽 옆면으로, 오른쪽 옆면이 아랫면으로, 아랫면이 왼쪽 옆면으로, 왼쪽 옆면이 주사위의 윗면이 될 것이다. 이런식으로 각각의 방향으로 주사위가 굴러갈 때, 주사위의 상태를 바꿔주면 된다.

본인은 이를 다음과 같이 구현하였다.

void updateDiceState(int d) {
	int d1 = dice[1];
	int d2 = dice[2];
	int d3 = dice[3];
	int d4 = dice[4];
	int d5 = dice[5];
	int d6 = dice[6];

	switch (d) {
	case 0 :
		dice[1] = d4;
		dice[4] = d6;
		dice[6] = d3;
		dice[3] = d1;
		break;
	case 1:
		dice[1] = d3;
		dice[3] = d6;
		dice[6] = d4;
		dice[4] = d1;
		break;
	case 2:
		dice[1] = d2;
		dice[2] = d6;
		dice[6] = d5;
		dice[5] = d1;
		break;
	case 3:
		dice[1] = d5;
		dice[5] = d6;
		dice[6] = d2;
		dice[2] = d1;
		break;
	}
}

초기 상태와 똑같이, dice[1] = 윗면, dice[2] = 뒷면, dice[3] = 오른쪽면, dice[4] = 왼쪽면, dice[5] = 앞면, dice[6] = 아랫면으로 고정해 둔 뒤, 주사위의 움직임에 따라서 각각의 면에 값만 갱신해 주었다.

이를 통해서 , dice[6]의 값, 즉, 주사위의 아랫면이 정해지게 되면, 이후에 주사위가 굴러갈 방향에 대해서 지정해준 후 #1 ~ #3의 과정을 계속해서 반복해 주면 된다.

 

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <queue>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
int n, m, k, answer;
int map[MAX][MAX];
bool visit[MAX][MAX];
 
int dice[7] = { 0, 1, 2, 3, 4, 5, 6 };
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void input() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
}
 
 
int reverseDir(int d) {
    switch (d) {
    case 0:
        return 1;
    case 1:
        return 0;
    case 2:
        return 3;
    case 3:
        return 2;
    }
}
 
int changeDir(int d, int ret) {
    if (ret > 0) {
        switch (d) {
        case 0:
            return 2;
        case 1:
            return 3;
        case 2:
            return 1;
        case 3:
            return 0;
        }
    }
    else if (ret < 0) {
        switch (d) {
        case 0:
            return 3;
        case 1:
            return 2;
        case 2:
            return 0;
        case 3:
            return 1;
        }
    }
    return d;
}
void getScore(int a, int b) {
    memset(visit, false, sizeof(visit));
 
    int num = map[a][b];
    int cnt = 1;
 
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    visit[a][b] = true;
 
    while (q.empty() == 0) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (map[nx][ny] == num && visit[nx][ny] == false) {
                    visit[nx][ny] = true;
                    cnt++;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    answer += (num * cnt);
}
 
void updateDiceState(int d) {
    int d1 = dice[1];
    int d2 = dice[2];
    int d3 = dice[3];
    int d4 = dice[4];
    int d5 = dice[5];
    int d6 = dice[6];
 
    switch (d) {
    case 0 :
        dice[1] = d4;
        dice[4] = d6;
        dice[6] = d3;
        dice[3] = d1;
        break;
    case 1:
        dice[1] = d3;
        dice[3] = d6;
        dice[6] = d4;
        dice[4] = d1;
        break;
    case 2:
        dice[1] = d2;
        dice[2] = d6;
        dice[6] = d5;
        dice[5] = d1;
        break;
    case 3:
        dice[1] = d5;
        dice[5] = d6;
        dice[6] = d2;
        dice[2] = d1;
        break;
    }
}
 
void solution() {
    int x = 0;
    int y = 0;
    int d = 0;
    for (int i = 0; i < k; i++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
            d = reverseDir(d);
            nx = x + dx[d];
            ny = y + dy[d];
        }
        getScore(nx, ny);
        updateDiceState(d);
        d = changeDir(d, dice[6] - map[nx][ny]);
        x = nx;
        y = ny;
    }
    cout << answer << endl;
}
 
void solve() {
    input();
    solution();
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    solve();
 
    return 0;
}