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

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

23288번: 주사위 굴리기 2

나머지 예제 생략

 

문제 이해

1. 주사위를 이동방향으로 움직인다. 없으면 (맵 밖으로 튀어나가면) 반대 방향으로 이동한다.

2. 도착한 데에서 점수 획득한다,

• 동서남북으로 이동할 수 있는 칸의 수를 구해야 한다. 즉, BFS를 하면서 최대 거리(C)를 구하면 된다. 
• 그리고 나머지는 하라는 대로 계산하면 되다. 

 

3. 이동방향을 결정하는데, dice.bottom과 map[y][x] 를 비교해서 결정하면 된다.

 

주사위를 이동하는 것만 잘 정의하면 된다. (Move())

 

주사위를 다음과 같이 보고 구조체를 초기화한다

각 방향으로 움직일 때 이 구조체가 어떻게 바뀌는지를 보면

이제 정해졌으니까 이대로 Move()에 구현하면 된다. 

 

작성 코드

#if 1
#include <stdio.h>
#include <string.h>

#define MAXN 20
#define EAST 0
#define SOUTH 1
#define WEST 2
#define NORTH 3

int N, M, K;
int map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
int pnt;

struct dicest {
	int bottom;
	int up;
	int east;
	int west;
	int north;
	int south;
} dice;
int diceY, diceX, diceD;

int dy[] = { 0, 1, 0, -1 }; // 동, 남, 서, 북
int dx[] = { 1, 0, -1, 0 };
int reverse[] = { WEST, NORTH, EAST, SOUTH };

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

void Init(void) {
	dice.bottom = 6;
	dice.up = 1;
	dice.east = 3;
	dice.west = 4;
	dice.north = 5;
	dice.south = 2;

	diceX = 1;
	diceY = 1;
	diceD = 0;
}

void Move(void) {
	int nEast, nWest, nSouth, nNorth, nBottom, nUp;
	int ny, nx;
	// diceD 방향으로 움직인다
	ny = dy[diceD] + diceY;
	nx = dx[diceD] + diceX;
	if (ny < 1 || ny > N || nx < 1 || nx > M) {
		// 칸이 없다면 방향 반대로
		diceD = reverse[diceD];
		ny = dy[diceD] + diceY;
		nx = dx[diceD] + diceX;
	}
	diceY = ny, diceX = nx;

	if (diceD == EAST) {
		nBottom = dice.east;
		nUp = dice.west;
		nWest = dice.bottom;
		nEast = dice.up;
		
		dice.west = nWest, dice.east = nEast;
		dice.bottom = nBottom, dice.up = nUp;
	}
	if (diceD == WEST) {
		nBottom = dice.west;
		nUp = dice.east;
		nWest = dice.up;
		nEast = dice.bottom;

		dice.west = nWest, dice.east = nEast;
		dice.bottom = nBottom, dice.up = nUp;
	}
	if (diceD == SOUTH) {
		nBottom = dice.north;
		nUp = dice.south;
		nSouth = dice.bottom;
		nNorth = dice.up;

		dice.north = nNorth, dice.south = nSouth;
		dice.bottom = nBottom, dice.up = nUp;
	}
	if (diceD == NORTH) {
		nBottom = dice.south;
		nUp = dice.north;
		nNorth = dice.bottom;
		nSouth = dice.up;

		dice.north = nNorth, dice.south = nSouth;
		dice.bottom = nBottom, dice.up = nUp;
	}
}

// queue
typedef struct ele {
	int y;
	int x;
}ELE;
ELE q[MAXN * MAXN * 10];
int wp, rp;
void enq(int y, int x) { q[wp].y = y; q[wp++].x = x; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }


int BFS(int sy, int sx) {
	// 초기화
	memset(visited, 0, sizeof(visited));
	wp = 0, rp = 0;

	int cnt = 1;
	int no = map[sy][sx];
	visited[sy][sx] = 1;
	enq(sy, sx);
	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + cur.y;
			int nx = dx[i] + cur.x;
			if (ny < 1 || ny > N || nx < 1 || nx > M) continue;
			if (map[ny][nx] != no) continue;
			if (visited[ny][nx] > 0) continue;
			visited[ny][nx] = 1;
			enq(ny, nx);
			cnt++;
		}
	}
	return cnt;
}

void Earn_Point(void) {
	
	int c = BFS(diceY, diceX);
	pnt += map[diceY][diceX] * c;
}

void Change_Direction(void) {
	int a = dice.bottom;
	int b = map[diceY][diceX];
	if (a > b) diceD = (diceD + 1) % 4;
	if (a < b) diceD = (diceD - 1 < 0) ? 3 : diceD - 1;
}

int main(void) {
	freopen("in.txt", "r", stdin);
	Get_Input();
	Init();
	for (int k = 0; k < K; k++) {
		Move(); // 굴러감
		Earn_Point(); // 점수 획득
		Change_Direction(); // 방향 전환
	}
	printf("%d", pnt);
	return 0;
}
#endif