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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지

www.acmicpc.net


문제 해결을 위한  과정

이 문제의 경우 골드 4 티어로 비교적 높은 난이도를 가지고 있지만 사실 구현으로 분류되는 문제의 특성상 차분하게 문제에서 제시한 조건을 따라가면 쉽게 해결할 수 있는 문제였습니다. 다만 주사위라는 공간지각 능력이 필요한 문제라서 조금 생각을 해야 합니다. 이 문제를 푸는 데 있어서 가장 중요한 것은 전개도입니다. 전개도 대로 주사위를 만들면 아래의 그림과 같습니다. 

윗면 1 아랫면 6 앞면 2 뒷면 5 왼쪽면 4 오른쪽면 3

이를 동쪽, 서쪽, 남쪽, 북쪽으로 돌리더라도 주사위의 특성상 마주보는 면의 합은 7입니다. 위 주사위 그림의 면에 배정된 숫자는 문제에서 주어진 조건 "주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여 있는 곳의 좌표는 (x, y)이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다." 를 반영한 것입니다. 즉 위치를 저렇게 잡은 후 모든 주사위의 면을 0으로 초기화합니다. 그 후 문제에서 테스트 케이스로 주어진 지도에 0행 0열에 주사위를 배치합니다. 첫 번째 예시에서 맵은 다음과 같습니다.

과정 및 주사위 그림은 다음과 같습니다.

1. 시작지점에 위치(0행 0열)

2. 명령이 4 이므로 남쪽으로 회전 1행 0열이 3 이므로 주사위의 밑면은 3, 윗면은 0이 됨 따라서 0 출력

 

3. 명령이 4 이므로 남쪽으로 회전 2행 0열이 5 이므로 주사위의 밑면은 5, 뒷면은 3, 윗면은 0이 됨 따라서 0 출력

4. 명령이 4 이므로 남쪽으로 회전 3행 0열이 7 이므로 주사위의 밑면은 7 뒷면은 5 윗면은 3이 됨 따라서 3 출력

5. 명령이 1 이므로 동쪽으로 회전 3행 1열이 8 이므로 주사위의 밑면은 8 왼쪽면은 7 오른쪽면은 3 뒷면은 5 윗면은 0 따라서 0 출력

이러한 과정을 반복한다.


문제 해결을 위한 팁

처음의 주사위의 전개도를 2차원 리스트의 형태로 구현한 후 문제를 해결하려 하였으나 예상보다 복잡해지는 바람에 다른 방법을 찾던 중 단순하게 일차원 리스트로 해결할 수 있음을 알게 되었고 해결방법은 다음과 같다. 먼저 리스트를 다음과 같이 설정한다.

dice = [0, 0, 0, 0, 0, 0]

윗면 1 아랫면 6 앞면 2 뒷면 5 왼쪽면 4 오른쪽면 3

그 후 이 그림을 보면서 항상 리스트의 0번째가 윗면, 1번째가 앞면, 2번째가 오른쪽면 이런 식으로 5번째가 아래쪽면이라는 것을 고정한 뒤 swap을 해준다. 즉 남쪽으로 한번 회전을 해주면 위의 그림에서 왼쪽 오른쪽면은 그대로 있고 나머지 4면이 회전을 하는 형태이다. 따라서 이를 이렇게 표현할 수 있다.

 

if 남쪽으로 회전할 시:

    dice[5], dice[1], dice[0], dice[4] = dice[1], dice[0], dice[4], dice[5] 

 

이를 전체의 경우에 적용하면 쉽게 해결할 수 있다. 소스코드는 아래와 같다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def movePos(dir):
  if dir == 1:
    dice[5], dice[2], dice[0], dice[3= dice[2], dice[0], dice[3], dice[5]
  elif dir == 2:
    dice[5], dice[3], dice[0], dice[2= dice[3], dice[0], dice[2], dice[5]
  elif dir == 3:
    dice[5], dice[4], dice[0], dice[1= dice[4], dice[0], dice[1], dice[5]
  else:
    dice[5], dice[1], dice[0], dice[4= dice[1], dice[0], dice[4], dice[5]
 
n, m, x, y, k = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
 
 
order = list(map(int, input().split()))
 
dice = [000000]
dx = [00-11]
dy = [1-100
 
for i in range(k):
  dir = order[i]
  nx = x + dx[dir-1]
  ny = y + dy[dir-1]
  if 0 > nx or 0 > ny or nx >= n or ny >= m:
    continue
  movePos(dir)
  if graph[nx][ny] == 0:
    graph[nx][ny] = dice[5]
  else:
    dice[5= graph[nx][ny]
    graph[nx][ny] = 0
  print(dice[0])
  x, y = nx, ny
cs

+ Recent posts