알고리즘 :: 백준 :: 시뮬레이션 :: 14499 :: 주사위 굴리기

문제

문제접근

문제 이해

• 시뮬레이션 유형의 골드 이상 난도를 가진 문제는 공통점이 있습니다.

  • 문제가 길어서 요구하는 바를 찾기 어려워집니다.
  • 문제에서 요구하는 조건이 많아 구현이 힘들어집니다.
  • TLE를 방지하기 위한 방법도 고려해야합니다.

• 시뮬레이션 유형은 반드시 문제를 읽으면서 줄치는 것 뿐만 아니라 자기 자신의 문장으로 새롭게 조건을 정리해서 쓰는 것이 좋습니다.

• 문제 조건은 다음과 같습니다.

  1. 좌표는 (r, c)로 표현.
     • 햇갈리시는 분이 많으시겠지만, 저는 원래 (y, x) 데카르트 좌표계를 애용합니다.
       이 문제는 (x, y)가 아니라 (y, x)로 좌표를 나타내야만 AC가 가능합니다.
  2. 가장 처음에 주사위 모든 면은 0.
     처음 주사위 위치의 지도 숫자도 0.
  3. 동쪽 1, 서쪽 2, 북쪽 3, 남쪽 4 → d[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
  4. 주사위가 이동한 칸이 0 임 → 주사위 밑면 숫자가 지도에 복사.
     주사위가 이동한 칸이 0 아님 → 지도 숫자가 주사위 밑면에 복사, 지도 숫자는 0으로 변경.
  5. 지도 바깥 이동 명령 (boundaryException)은 무시.
  6. 이동했을 때마다 주사위 윗면 값 출력하기.

• 문제는 복잡했지만, 위 여섯 줄로 간단하게 정리할 수 있습니다.
  주사위 이동과 경계조건 검사 그리고 매 이동 때 해야하는 작업이 간단해 쉬운 문제로 바뀝니다.

• 주사위를 동, 서, 남, 북으로 이동할 때 어떤 면이 어떻게 바뀌어야 하는지 꼭 생각해보세요.

• 주사위를 구현하는 방법은 여러가지 있습니다.

  1. 3차원 배열을 쓴다.

     → 떠올리지도 마세요.

  2. 구조체를 쓴다.

     → 제가 사용한 방법입니다. 코드 가독성이 훨씬 좋아지고 메모리 낭비도 없어 좋아하는 방법입니다.

  3. 6칸짜리 1차원 배열을 쓴다.

코드

#include <cstdio>

typedef struct Dice {
	int up		= 0, down	= 0;
	int front	= 0, back	= 0;
	int left	= 0, right	= 0;
} Dice;

Dice dice;
int N, M, X, Y, K, map[20][20];
constexpr int d[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

void roll(int op) {
	int tmp = dice.down;
	switch(op) {
	case 0:	// east
		dice.down	= dice.right;
		dice.right	= dice.up;
		dice.up		= dice.left;
		dice.left	= tmp;
		break;
	case 1:	// west
		dice.down	= dice.left;
		dice.left	= dice.up;
		dice.up		= dice.right;
		dice.right	= tmp;
		break;
	case 2:	// north
		dice.down	= dice.back;
		dice.back	= dice.up;
		dice.up		= dice.front;
		dice.front	= tmp;
		break;
	case 3:	// south
		dice.down	= dice.front;
		dice.front	= dice.up;
		dice.up		= dice.back;
		dice.back	= tmp;
		break;
	}
}
int main() {
	scanf("%d %d %d %d %d", &N, &M, &Y, &X, &K);
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			scanf("%d", &map[y][x]);
	int ny, nx, op;
	for (int i = 0; i < K; ++i) {
		scanf("%d", &op);
        	op--;
		ny = Y + d[op][0], nx = X + d[op][1];
        	// Boundary exception
		if (N <= ny || ny < 0 || M <= nx || nx < 0) continue;
        	roll(op);
        	if (map[ny][nx]) {
            		dice.down = map[ny][nx];
            		map[ny][nx] = 0;
       		} 
        	else map[ny][nx] = dice.down;
        	Y = ny, X = nx;
        	printf("%d\n", dice.up);
	}
}

결과