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

Approach

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

해당 문제에서 주요 구현사항은 아래와 같다.

• 주어진 방향에 따른 주사위 굴리기 → 현재 위치 (x, y) 갱신

• 도착한 곳의 점수 계산 → BFS

• 주사위 상태 갱신

• 주사위 방향 갱신

for (int level = 1; level <= K; level++)
{
    int nextX = cur.x + dx[dir];
    int nextY = cur.y + dy[dir];

    // map[][]을 벗어나는 경우 반대방향으로 이동
    if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
    {
        dir = reverseDir[dir];
        nextX = cur.x + dx[dir];
        nextY = cur.y + dy[dir];
    }
   
    BFS(nextX, nextY, level); // 점수 계산
    updateDice(dir); // 주사위 상태 변화
    changeDir(dice[6], map[nextX][nextY]); // 주사위 방향 회전
    cur.set(nextX, nextY);
}

 

점수 계산

BFS 구현에 있어서 문제 요구 조건 중

인접한 영역에서 처음 시작했던 곳과 동일한 점수만 이동할 수 있다.

그리고 해당 영역만큼 점수를 얻는데, {개수 * 칸에 적힘 점수}로 계산 가능

void BFS(int sX, int sY, int lev)
{
    int val = map[sX][sY];
    ans += val;

    queue<pair<int, int>> que;
    que.push(make_pair(sX, sY));
    visit[sX][sY] = lev;

    while (que.empty() == 0) {
        Node node = { que.front().first, que.front().second };
        que.pop();

        // 연속된 지점을 이동
        for (int i = 0; i < 4; i++) {
            int nextX = node.x + dx[i];
            int nextY = node.y + dy[i];

            // map[][]을 벗어나는 경우
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;

            // 같은 숫자가 아닌 경우
            if (map[nextX][nextY] != val) continue;

            // 현재 lev의 BFS에서 중복방문인 경우
            if (visit[nextX][nextY] >= lev) continue;

            ans += val;
            visit[nextX][nextY] = lev; // 방문표시
            que.push(make_pair(nextX, nextY));
        }
    }
}

BFS 탐색에서는 이동가능한 영역인지 확인하여 진행한다.

→ map[][] 범위, 중복 방문, 칸에 적힌 점수가 동일한지

→ 성능 확보를 위해 visit[][]를 초기화 하지 않고 lev 변수로 처리

   실제 코딩 테스트에서도 첫번째 문제이기에 

    BFS마다 초기화해주어도 시간제한을 만족했을 것이다. 😒

▶ BFS (Breadth-First Search, 너비 우선 탐색)

BFS (Breadth-First Search, 너비 우선 탐색)

 

주사위 구현

주사위 전개도는 dice[7]로 구현

각각의 방향을 설정하고 주사위 방향에 맞춰 방향 갱신

switch~case 문이나 if문으로 구현해도 되나

규치적인 변화이기 때문에 LUT(Look Up Table) 활용

이 부분이 해당 문제의 까다로운 부분이 될 것 같다.

주사위를 Code로 구현하는 문제인데,

실수하기 쉬운 부분이면서 디버깅하기 어려운 부분이 될 수 있다.

* 주사위가 벽에 닿게 된다면 반대방향으로 바꿔주는데 유의한다.

 

주사위 굴리기 14499 문제를 풀어보았다면 도움되었을 것 같네요

▶ BOJ 14499 주사위 굴리기

[BOJ] 백준 14499 주사위 굴리기

---

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	int x, y;

	void set(int _x, int _y)
	{
		x = _x, y = _y;
	}
} cur;

enum
{
	EAST,
	WEST,
	SOUTH,
	NORTH
};

// 동서남북
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };

// 주사위 반대방향 전환시
const int reverseDir[] = { WEST, EAST, NORTH, SOUTH };

// 주사위 굴리기에 따른 상태 변화시
const int changeState[4][7] = { {0, 4, 2, 1, 6, 5, 3},  // 동쪽 이동
							  {0, 3, 2, 6, 1, 5, 4},    // 서쪽 이동
							  {0, 2, 6, 3, 4, 1, 5},    // 남쪽 이동
							  {0, 5, 1, 3, 4, 6, 2} };  // 북쪽 이동

// 현재 방향 기준에서 회전에 따른 새로운 방향
const int rotateDir[2][4] = { {SOUTH, NORTH, WEST, EAST},
							  {NORTH, SOUTH, EAST, WEST} };

const int MAX_NM = 25;
int N, M, K, ans, dir;
int dice[7] = { 0, 1, 2, 3, 4, 5, 6 };
int map[MAX_NM][MAX_NM], visit[MAX_NM][MAX_NM];

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
}

void BFS(int sX, int sY, int lev)
{
	int val = map[sX][sY];
	ans += val;

	queue<pair<int, int>> que;
	que.push(make_pair(sX, sY));
	visit[sX][sY] = lev;

	while (que.empty() == 0) {
		Node node = { que.front().first, que.front().second };
		que.pop();

		// 연속된 지점을 이동
		for (int i = 0; i < 4; i++) {
			int nextX = node.x + dx[i];
			int nextY = node.y + dy[i];

			// map[][]을 벗어나는 경우
			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;

			// 같은 숫자가 아닌 경우
			if (map[nextX][nextY] != val) continue;

			// 현재 lev의 BFS에서 중복방문인 경우
			if (visit[nextX][nextY] >= lev) continue;

			ans += val;
			visit[nextX][nextY] = lev; // 방문표시
			que.push(make_pair(nextX, nextY));
		}
	}
}

void updateDice(int d)
{
	int pre[7] = { 0, };
	for (int i = 1; i <= 6; ++i)
	{
		pre[i] = dice[i];
	}

	for (int i = 1; i <= 6; ++i)
	{
		dice[i] = pre[changeState[d][i]];
	}
}

void changeDir(int A, int B)
{
	if (A == B) return;

	// A > B 인 경우 시계방향, 그렇지 않으면 반시계 방향
	int mode = A > B ? 0 : 1;
	dir = rotateDir[mode][dir];
}

int main()
{
	// freopen("Input.txt", "r", stdin);
	input();

	for (int level = 1; level <= K; level++)
	{
		int nextX = cur.x + dx[dir];
		int nextY = cur.y + dy[dir];

		// map[][]을 벗어나는 경우 반대방향으로 이동
		if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
		{
			dir = reverseDir[dir];
			nextX = cur.x + dx[dir];
			nextY = cur.y + dy[dir];
		}
		
		BFS(nextX, nextY, level);
		updateDice(dir);
		changeDir(dice[6], map[nextX][nextY]);
		cur.set(nextX, nextY);
	}

	printf("%d\n", ans);
}

이동 횟수 K가 크지 않은 수라면 위와 같은 방법으로 구해도 충분하다.

성능개선을 해야한다면 (x, y) 좌표에서 얻을 수 있는 점수를

시작전에 모두 구해서 score[][]에 미리 저장하는 것이다.

주어지는 방향에 따라 되돌아오는 지점도 있을 수 있으며

점수가 같으면서 인접한 영역을 주사위 굴릴때 마다 BFS 할 필요는 없다.

 

코딩 테스트 A형 특성상 시간 효율보다는 문제 풀이 개수가 중요하기 때문에

다른 문제도 풀고 리팩토링 시간을 가져보면 좋을 것 같네요.

▶ 삼성 SW 기출 모음

▶ 삼성 SW 코딩 테스트 준비(A형)