[BOJ] 23288번 주사위 굴리기 2 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

주사위 관련해서는 이전에 풀이했던 기억이 있어서 이동하는 코드를 그래도 빠르게 짤 수 있었다. 다만, 더 나은 방법이 없는지 한번 찾아봐야겠다.
=> 특별히 더 나은 방법은 없어 보인다!

주사위 번호 한 방향을 다른 방향과 중복해서 적는 실수를 해서 마지막 테스트 케이스를 틀렸다. 마지막 테스트 케이스가 없었으면 못 찾고 제출했을거다. 테스트 케이스 넣기전 코드 전체 검토할때 좀 더 집중해서 꼼꼼히 하자.

연결된 개수 구할때 BFS를 이용했는데 N,M<=20이라는 조건이 있어서 조금 비효율적으로 짰는데, 효율적으로 짤 방법을 한번 고민해봐야겠다.

풀이에 약 1시간 걸렸는데 IDE없었으면 더 걸렸을거다. IDE 의존성을 언젠가는 줄일 필요가 있을 듯.

from collections import deque

DX_DY = [(-1,0),(0,1),(1,0),(0,-1)]
NORTH, EAST, SOUTH, WEST = 0,1,2,3 # +1은 시계방향,-1은 반시계방향
INVERSE_DIRECTION = {NORTH: SOUTH, EAST: WEST, SOUTH: NORTH, WEST: EAST}


class Dice:
    def __init__(self):
        # x,y 좌표(인덱스 0부터!)
        self.x = 0
        self.y = 0

        # 해당방향에 적힌 주사위 번호
        self.top = 1 # 위에서 보이는 윗면
        self.bottom = 6
        self.left = 4
        self.right = 3
        self.up = 2
        self.down = 5 # !6으로 잘못썼었다.

        # 방향
        self.direction = EAST # 처음은 동쪽

        # 점수
        self.score = 0
    
    def move(self):
        # 이동방향 막혀있으면 반대로 변경
        dx,dy = DX_DY[self.direction]
        move_x,move_y = self.x+dx, self.y+dy
        if not is_valid(move_x,move_y):
            self.direction = INVERSE_DIRECTION[self.direction]
        
        # 주사위 좌표 변경
        dx,dy = DX_DY[self.direction]
        self.x, self.y = self.x+dx, self.y+dy

        # 주사위 칸 번호 변경
        if self.direction == NORTH:
            self.top, self.up, self.bottom, self.down =\
                self.down, self.top, self.up, self.bottom
        elif self.direction == SOUTH:
            self.top, self.up, self.bottom, self.down =\
                self.up, self.bottom, self.down, self.top
        elif self.direction == EAST:
            self.top, self.right, self.bottom, self.left =\
                self.left, self.top, self.right, self.bottom
        elif self.direction == WEST:
            self.top, self.right, self.bottom, self.left =\
                self.right, self.bottom, self.left, self.top

def is_valid(x,y):
    """범위안에 있는지만(인덱스 0부터!)"""
    if 0<=x<N and 0<=y<M:
        return True
    return False

def get_connected_cnt(x,y):
    """(x,y)에서 같은수로 연결된 수 반환(BFS), O(N*M)"""
    visited = [[False]*M for _ in range(N)]
    cnt = 1 # (x,y)는 포함
    visited[x][y] = True
    queue = deque([(x,y)])

    while queue:
        x,y = queue.pop()
        for dx, dy in DX_DY:
            check_x = x+dx
            check_y = y+dy
            if is_valid(check_x,check_y) and not visited[check_x][check_y]\
                and graph[x][y] == graph[check_x][check_y]:
                cnt += 1
                visited[check_x][check_y] = True
                queue.appendleft((check_x,check_y))

    return cnt


N,M,K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dice = Dice()

# 1. 점수판 구하기(연결된 같은칸수)
score = [[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        connected_cnt = get_connected_cnt(i,j)
        score[i][j] += connected_cnt*graph[i][j]

# 2. 주사위 이동
for _ in range(K):
    # 주사위 이동(막히면 반대방향으로)
    dice.move()

    # 점수 획득
    dice.score += score[dice.x][dice.y]

    # 이동방향 결정
    A = dice.bottom
    B = graph[dice.x][dice.y]
    if A > B: # 시계방향
        dice.direction += 1
    elif A < B:
        dice.direction -= 1
    dice.direction %= 4


print(dice.score)