[백준 23288] 주사위 굴리기 2 (Python 풀이)

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

23288번: 주사위 굴리기 2

---

이 문제는 '주사위 방향에 따른 이동'을 풀어내는 것과 BFS 알고리즘을 활용하면 풀 수 있습니다.

풀이

주사위 이동

주사위 이동에 대한 함수는 따로 알고리즘으로 풀어내기 보다는 케이스가 4개뿐이기 때문에 규칙을 찾아 하드코딩으로 구현하였습니다.  

주사위의 이동은 좌우로 움직이는 경우와 상하로 움직이는 경우로 나눌 수 있습니다. 그림으로 표현하면 다음과 같습니다.

주사위가 좌우로 움직이는 경우

주사위가 상하로 움직이는 경우(예시는 아래쪽)

따라서 주사위와 주사위 이동에 대한 함수 move_dice()를 다음과 같이 정의합니다.

UP, LEFT, DOWN, RIGHT = 0, 1, 2, 3
dice = [
    [ -1,  2, -1],
    [  4,  1,  3],
    [ -1,  5, -1],
    [ -1,  6, -1]
]
def move_dice(dir):
    global dice
 
    if dir == RIGHT:
        tmp = dice[1][2]
        dice[1] = [dice[3][1], dice[1][0], dice[1][1]]
        dice[3][1] = tmp
    elif dir == LEFT:
        tmp = dice[1][0]
        dice[1] = [dice[1][1], dice[1][2], dice[3][1]]
        dice[3][1] = tmp
    elif dir == UP:
        tmp = dice[0][1]
        dice[0][1] = dice[1][1]
        dice[1][1] = dice[2][1]
        dice[2][1] = dice[3][1]
        dice[3][1] = tmp
    elif dir == DOWN:
        tmp = dice[3][1]
        dice[3][1] = dice[2][1]
        dice[2][1] = dice[1][1]
        dice[1][1] = dice[0][1]
        dice[0][1] = tmp

 

주사위의 정보를 dice라는 배열로 저장하고, 주사위의 방향(dir)에 따라 주사위의 값들이 이동하게 됩니다.

BFS

방향에 따라 이동한 후에는 해당 위치에서 BFS를 이용하여 점수를 계산합니다.

해당 좌표와 이어진 좌표에서 같은 점수를 가지는 좌표의 개수와 해당 좌표의 점수를 곱하여 반환합니다. 이동한 좌표에서 점수를 반환하는 함수 get_score_by_bfs()는 다음과 같습니다.

def get_score_by_bfs(sy, sx, B):
    used = [[False] * M for _ in range(N)] # check if loc is visited loc
    cnt = 0
    q = deque() # from collections import deque
    q.append((sy, sx))
    used[sy][sx] = True
    while q:
        y, x = q.pop()
        cnt += 1 # count 추가
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
 
            if ny < 0 or nx < 0 or ny >= N or nx >= M or used[ny][nx]:
                continue
            if board[ny][nx] == B:
                used[ny][nx] = True
                q.append((ny, nx))
    return cnt * B # 점수 = B x B의 개수
 

요구사항에 따라 구현

이제 두 함수를 이용하여 요구사항에 맞게 코드를 구현하면 됩니다.

loc = (0, 0)
result = 0
for i in range(K):
    ny = loc[0] + dy[dir]
    nx = loc[1] + dx[dir]
 
    if ny < 0 or nx < 0 or ny >= N or nx >= M: # 이동할 수 없는 경우
        dir = (dir + 2) % 4 # 방향을 180도 바꿔서 이동
        ny = loc[0] + dy[dir]
        nx = loc[1] + dx[dir]
 
    loc = (ny, nx)
    move_dice(dir) # 주사위 이동
    B = board[ny][nx] # 이동한 좌표의 숫자
    score = get_score_by_bfs(ny, nx, B) # BFS를 이용하여 점수 계산 
    result += score
 
    #맨 아랫쪽 주사위 값(A)과 이동한 좌표의 숫자(B) 비교
    A = dice[3][1]
    if A > B: dir = (dir - 1) % 4
    elif A < B:dir = (dir + 1) % 4
 
print(result)
 

 

설명은 주석으로 대체하겠습니다. 

---

전체 소스 코드

from collections import deque
 
N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
 
dy = (-1, 0, 1, 0)
dx = ( 0,-1, 0, 1)
UP, LEFT, DOWN, RIGHT = 0, 1, 2, 3
dir = RIGHT
dice = [
    [ -1,  2, -1],
    [  4,  1,  3],
    [ -1,  5, -1],
    [ -1,  6, -1]
]
def move_dice(dir):
    global dice
 
    if dir == RIGHT:
        tmp = dice[1][2]
        dice[1] = [dice[3][1], dice[1][0], dice[1][1]]
        dice[3][1] = tmp
    elif dir == LEFT:
        tmp = dice[1][0]
        dice[1] = [dice[1][1], dice[1][2], dice[3][1]]
        dice[3][1] = tmp
    elif dir == UP:
        tmp = dice[0][1]
        dice[0][1] = dice[1][1]
        dice[1][1] = dice[2][1]
        dice[2][1] = dice[3][1]
        dice[3][1] = tmp
    elif dir == DOWN:
        tmp = dice[3][1]
        dice[3][1] = dice[2][1]
        dice[2][1] = dice[1][1]
        dice[1][1] = dice[0][1]
        dice[0][1] = tmp
 
def get_score_by_bfs(sy, sx, B):
    used = [[False] * M for _ in range(N)]
    cnt = 0
    q = deque()
    q.append((sy, sx))
    used[sy][sx] = True
    while q:
        y, x = q.pop()
        cnt += 1 # count 추가
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
 
            if ny < 0 or nx < 0 or ny >= N or nx >= M or used[ny][nx]:
                continue
            if board[ny][nx] == B:
                used[ny][nx] = True
                q.append((ny, nx))
    return cnt * B # 점수 = B x B의 개수
 
loc = (0, 0)
result = 0
for i in range(K):
    ny = loc[0] + dy[dir]
    nx = loc[1] + dx[dir]
 
    if ny < 0 or nx < 0 or ny >= N or nx >= M: # 이동할 수 없는 경우
        dir = (dir + 2) % 4 # 방향을 180도 바꿔서 이동
        ny = loc[0] + dy[dir]
        nx = loc[1] + dx[dir]
 
    loc = (ny, nx)
    move_dice(dir) # 주사위 이동
    B = board[ny][nx] # 이동한 좌표의 숫자
    score = get_score_by_bfs(ny, nx, B) # BFS를 이용하여 점수 계산
    result += score
 
    #맨 아랫쪽 주사위 값(A)과 이동한 좌표의 숫자(B) 비교
    A = dice[3][1]
    if A > B: dir = (dir - 1) % 4
    elif A < B:dir = (dir + 1) % 4
 
print(result)
 
 
 

 

 

감사합니다.