공부/PS (백준)

[BOJ] 23288 주사위 굴리기 2

happyst 2022. 4. 24. 21:07

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

 

23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

 

#include <stdio.h>
#include <queue>

#define MAX	21

using namespace std;

int N, M, K;
int BOARD[MAX][MAX];
int visited[MAX][MAX];

int dr[] = { -1,0,1,0 }; // 북동남서
int dc[] = { 0,1,0,-1 };

struct DICE {
	int r, c, bottom, top, front, back, left, right, dir;
};

DICE dice;

void print_dice()
{
	printf(">> print_dice()\n");
	printf("bottom %d top %d front %d back %d left %d right %d\n\n", dice.bottom, dice.top, dice.front, dice.back, dice.left, dice.right);
}

void roll_dice(int dir)
{
	// dir 방향으로 주사위를 굴린다
	DICE copydice = dice;

	if (dir == 0) // 북
	{
		dice.bottom = copydice.back;
		dice.top = copydice.front;
		dice.front = copydice.bottom;
		dice.back = copydice.top;
	}
	else if (dir == 1) // 동
	{
		dice.bottom = copydice.right;
		dice.top = copydice.left;
		dice.left = copydice.bottom;
		dice.right = copydice.top;
	}
	else if (dir == 2) // 남
	{
		dice.bottom = copydice.front;
		dice.top = copydice.back;
		dice.front = copydice.top;
		dice.back = copydice.bottom;
	}
	else if (dir == 3) // 서
	{
		dice.bottom = copydice.left;
		dice.top = copydice.right;
		dice.left = copydice.top;
		dice.right = copydice.bottom;
	}
}

int change_dir(int dir, int type) // type: 0(반전), 1: cw 90도, 2: ccw 90도
{
	if (type == 0)
		return (dir + 2) % 4;
	else if (type == 1)
		return (dir + 1) % 4;
	else if (type == 2)
		return (dir + 3) % 4;
}

int bfs(int r, int c)
{
	int board_num = BOARD[r][c];
	int cnt = 1;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			visited[i][j] = 0;
		}
	}

	queue <pair<int, int> > q;
	q.push(make_pair(r, c));
	visited[r][c] = 1;

	while (!q.empty())
	{
		int cur_r = q.front().first;
		int cur_c = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++)
		{
			int nr = cur_r + dr[k];
			int nc = cur_c + dc[k];

			if (nr <= 0 || nr > N || nc <= 0 || nc > M || visited[nr][nc] || BOARD[nr][nc] != board_num) continue;
			q.push(make_pair(nr, nc));
			visited[nr][nc] = 1;
			cnt++;
		}
	}
	return cnt;
}

int getScore()
{
	int board_num = BOARD[dice.r][dice.c];
	int cnt = bfs(dice.r, dice.c);
	int board_score = board_num * cnt;
	return board_score;
}

void setDirecton()
{
	int board_num = BOARD[dice.r][dice.c];
	int bottom_num = dice.bottom;

	if (bottom_num > board_num)
	{
		dice.dir = change_dir(dice.dir, 1);
	}
	else if (bottom_num < board_num)
	{
		dice.dir = change_dir(dice.dir, 2);
	}
}

bool inBounds(int r, int c, int dir)
{
	int nr = r + dr[dir];
	int nc = c + dc[dir];

	if (nr <= 0 || nr > N || nc <= 0 || nc > M) return false;
	return true;
}

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

	dice.r = 1;
	dice.c = 1;
	dice.bottom = 6;
	dice.top = 1;
	dice.front = 5;
	dice.back = 2;
	dice.left = 4;
	dice.right = 3;
	dice.dir = 1; // 동쪽
}

int solve()
{
	int score = 0;
	while (K--)
	{
		if (!inBounds(dice.r, dice.c, dice.dir))
		{
			dice.dir = change_dir(dice.dir, 0);
		}
		
		int nr = dice.r + dr[dice.dir];
		int nc = dice.c + dc[dice.dir];
		roll_dice(dice.dir);
		dice.r = nr;
		dice.c = nc;

		score += getScore();

		setDirecton();
	}
	return score;
}


int main(void)
{
	input();
	int answer = solve();
	printf("%d\n", answer);
	return 0;
}

 

하..ㅎㅎ

마지막 테스트 케이스를 제외한 나머지 테스트 케이스는 다 통과하길래... 프린트까지 다 찍어가면서 살펴봤는데

visited 배열 초기화에 문제가 있었다..ㅎㅎ

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			visited[i][j] = 0;
		}
	}

N * M이 아닌 N * N으로 초기화를 해주고 있었던것,,,

 

제발 시험장에 가서는 이런 실수 하지 말자.

실수할 일 없게 N, M을 R, C로 바꿔서 푸는 것도 좋은듯하다.