문제 - 주사위 굴리기2

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

문제 설명

링크 참조

입력
첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다.

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다.

출력
첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다.

🤨풀이를 어떻게 생각했는가?

1. 문제의 조건

• 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
• 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다. 칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다.
  • (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다.
  • 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.
• 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
  • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
  • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
  • A = B인 경우 이동 방향에 변화는 없다.

2. 고민 과정

• 굴러야 하는 방향으로 칸이 없다면, 반대로 한 칸 굴러야 한다는 조건은 윗 부분에서 확인해 줘야 할 것 같다.
• 도착했을 때 점수를 획득하는데, 같은 숫자가 써져 있는 칸 모두를 구해서 곱해줘야 한다. 탐색을 통해 동서남북에 있는 같은 수인 칸의 개수를 구해주면 될 것 같다.
• 다음 이동 방향은 주사위 아랫면의 숫자와 현재 칸의 숫자를 비교해서 정해준다. 한 사이클이 종료될 시점에 적용해주면 될 것 같다.

3. 주요 포인트

• 주사위 이동 후, 각 면의 숫자가 어떻게 바뀌는지 파악하고, 반영해줘야 한다.
• 도착 칸의 같은 숫자의 갯수를 파악하고, 점수를 구해줘야 한다.

4. 구현 과정

1. 주사위 이동시의 변화를 알아야 한다. 주사위 도면은 아래와 같은 방식으로 생각한다. (리스트 작성시, dice = [0, 1, 2, 3, 4, 5] 와 같음.)
   

2. 위의 주사위를 가지고, 각각 동, 서, 남, 북으로 움직였을 시 숫자의 변화를 파악한다. (맨 왼쪽의 잘린 숫자는 5이다.)
   이로써 주사위가 이동 후, 어떤 식으로 숫자의 변화가 있는지 알 수 있다.

3. 각 이동시 변화가 담겨있는 move_map 배열을 만들어 준다.

move_map = [[4, 1, 3, 6, 5, 2], [3, 2, 6, 4, 1, 5],
[2, 6, 3, 1, 5, 4], [5, 2, 1, 4, 6, 3]]

4. move_dice 라는 함수를 만들어 이동시마다 주사위의 변화를 반영시켜준다.

def move_dice(direction):
    global dice
    temp = dice[:]
    for i in range(len(dice)):
        temp[i] = dice[move_map[direction][i]]
    dice = temp[:]

5. 점수를 세는 함수인 point_count를 만들어준다. BFS를 이용해, 현재 도착한 칸이 같은 숫자라면, 체크해주고 count에 1을 더해준다. 끝에는 현재 count에 그 칸의 값인 B를 곱해 return 해준다.

def point_count(cx, cy, B):
    q = deque()
    check = [[False] * M for _ in range(N)]
    cnt = 0
    q.append((cy, cx))
    check[cy][cx] = True
    while q:
        y, x = q.popleft()
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ny < 0 or nx < 0 or ny >= N or nx >= M or check[ny][nx]:
                continue
            if Board[ny][nx] == B:
                check[ny][nx] = True
                q.append((ny, nx))
    return cnt * B

6. 끝으로, 반복문을 통해 주사위가 이동할 시 일어나는 과정들을 적용시켜준다.

#전체코드# 
from collections import deque


def move_dice(direction):
    global dice
    temp = dice[:] #temp에 현재 주사위 숫자 위치를 복사
    for i in range(len(dice)):
    	# 이동 후 주사위의 숫자와 현재 주사위 숫자의 위치를 교체해준다.
        temp[i] = dice[move_map[direction][i]] 
    dice = temp[:] #다음 주사위 숫자 위치를 dice로 복사


def point_count(cx, cy, B):
    q = deque()
    check = [[False] * M for _ in range(N)]
    cnt = 0
    q.append((cy, cx))
    check[cy][cx] = True
    while q:
        y, x = q.popleft()
        cnt += 1 #같은 칸이 하나 있는 것이기 때문에 +1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #이동할 수 없거나 이미 확인된 곳이라면 넘어간다.
            if ny < 0 or nx < 0 or ny >= N or nx >= M or check[ny][nx]:
                continue
            #이동 후 현재 칸의 값과 같은 숫자라면 check해주고 q에 넣어준다.
            if Board[ny][nx] == B:
                check[ny][nx] = True
                q.append((ny, nx))
    return cnt * B


N, M, K = map(int, input().split())
Board = [list(map(int, input().split())) for _ in range(N)]
# dx, dy를 동,서,남,북 순으로 입력받을 수 있게 세팅.
dx = [1, 0, -1, 0] 
dy = [0, 1, 0, -1]
direction = 0
dice = [6, 4, 2, 3, 5, 1] #현재 주사위의 숫자(구현과정 1번 그림 참고)
# move_map = [[4, 1, 3, 6, 5, 2], [3, 2, 6, 4, 1, 5], [2, 6, 3, 1, 5, 4], [5, 2, 1, 4, 6, 3]]
move_map = [[], [], [], []]
move_map[0] = [3, 0, 2, 5, 4, 1]
move_map[1] = [4, 1, 0, 3, 5, 2]
move_map[2] = [1, 5, 2, 0, 4, 3]
move_map[3] = [2, 1, 5, 3, 0, 4]
#dx, dy가 동 서 남 북 순이기 때문에 주사위의 이동 후 숫자도 순서대로 맞춰줌
#		  0  1  2  3


current_location = (0, 0) #시작 위치
total_point = 0
for i in range(K):
	# 처음은 오른쪽으로 향하기 때문에, direction = 0 그대로 더해줌
    ny = current_location[0] + dy[direction] 
    nx = current_location[1] + dx[direction]
	# 갈 수 없는 상황일 경우, 반대로 바꿔줌
    if ny < 0 or nx < 0 or ny >= N or nx >= M:
    	#비트연산자로 반대 방향으로 바꿔준 후, ny, nx를 다시 조정
        direction = direction ^ 2
        ny = current_location[0] + dy[direction]
        nx = current_location[1] + dx[direction]
	
    current_location = (ny, nx) #현재 위치를 ny, nx로 입력
    move_dice(direction) # 주사위 숫자 변경
    B = Board[ny][nx] # 현재 칸의 숫자 값
    point = point_count(nx, ny, B)
    total_point += point
    A = dice[0] # 주사위의 아랫면
    if A > B: #주사위 아랫면이 더 클 경우 시계방향 90도
        direction = (direction + 1) % 4
    elif A < B: #주사위 아랫면이 더 작을 경우 반시계방향 90도
        direction = (direction - 1) % 4

print(total_point)

🤔생각

• 머리로만 생각하면 굴릴 때마다 점수 구하고, 주사위 숫자만 바꿔주고, 다음 방향만 정해주면 되는 것 같은데 하나씩 로직을 구현하는 과정이 역시 쉽지 않았다..

• 막상 하고나니 코드 길이도 짧고, 직관적으로 생겨서 다음엔 더 쉽게 풀 수 있을 것 같다

• 1000번 반복해야 하는 마지막 테스트 케이스에서 틀려서 시간이 오래 걸렸는데, 주사위 이동 방향과 dx, dy를 맞춰주지 않아서 그랬었다! 다행인건 함수를 하나씩 짤때마다 맞는지 틀리는지 확인해줘서 엄청 헤매진 않았다.

• 찾았다!숭이 이모티콘을 좋아하는 분의 영상을 보고 도움을 많이 받았다...😅