공부/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로 바꿔서 푸는 것도 좋은듯하다.