https://www.acmicpc.net/problem/14499
문제 해결을 위한 과정
이 문제의 경우 골드 4 티어로 비교적 높은 난이도를 가지고 있지만 사실 구현으로 분류되는 문제의 특성상 차분하게 문제에서 제시한 조건을 따라가면 쉽게 해결할 수 있는 문제였습니다. 다만 주사위라는 공간지각 능력이 필요한 문제라서 조금 생각을 해야 합니다. 이 문제를 푸는 데 있어서 가장 중요한 것은 전개도입니다. 전개도 대로 주사위를 만들면 아래의 그림과 같습니다.
이를 동쪽, 서쪽, 남쪽, 북쪽으로 돌리더라도 주사위의 특성상 마주보는 면의 합은 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]
그 후 이 그림을 보면서 항상 리스트의 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 = [0, 0, 0, 0, 0, 0]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
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 |
'알고리즘 > 백준' 카테고리의 다른 글
백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.12 |
---|---|
백준 알고리즘 11723번: 집합(Python) (0) | 2022.01.10 |
백준 알고리즘 2941번: 크로아티아 알파벳(Python) (0) | 2022.01.07 |
백준 알고리즘 14659번: 한조서열정리하고옴ㅋㅋ(Python) (0) | 2022.01.06 |
백준 알고리즘 1080번: 행렬(Python) (0) | 2022.01.06 |