[백준] No.23288 주사위 굴리기 2 01

 

23288번: 주사위 굴리기 2

상어 초등학교와 같은 빡구현 문제다.

빡구현 문제도 여러 번 풀어봐야 다른 문제나 프로젝트에서도 능숙하게 코딩할 수 있다고 생각하긴 한다.

흔히 말하는 맨 땅에 헤딩을 많이 해봐야 실력이 느는 느낌이다.

 

근데 이번 문제는 해석하는데 굉장히 오래 걸렸다... 뭔가 적혀있는 게 여러 해석의 여지가 있다고 할까.

전개도가 있다고 할 때 어떤 식으로 접어야 하는지,

동쪽을 바라보는 방향이 놓여져 있다는 것이 주사위의 입장인지 바라보는 사람 입장인지,

회전할 때 이동 방향만 바뀌는 건지 주사위도 같이 회전하는 건지,

동서남북 방향으로 연속해서 이동할 수 있는 칸의 수는 대체 뭘 의미하는 건지...

 

 

해석을 해서 예제 입력 1을 실제로 그리면 위와 같은 상황이 된다.

전개도는 위의 주사위의 형태로 접히고, 3도 위의 그림처럼 놓인다.

주사위는 굴러가기만 할 뿐, 실제로 회전하지는 않는다. 위의 그림을 생각하면서 코드 작성을 해보자. 

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Function ----------
def check_range():
    return

def roll_dice(dir):
    return

def change_direction(dir, dice_num, map_num):
    return

def BFS(x, y, value):
    return

# ---------- Main ----------
row, col, move = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(row)]

for _ in range(move):
    check_range()

    dice_map = roll_dice(cur_dir)

    answer += BFS(x, y, graph[x][y])

    cur_dir = change_direction(cur_dir, dice_map[-1], graph[x][y])
    
print(answer)

이런 문제를 풀 때, 전체적인 흐름을 파악하는 게 굉장히 중요하다.

문제를 순서대로 따라가다보면, 주사위가 이동하고 범위를 벗어났는지 확인한다.

주사위의 전개도도 바꾸고,  방향 전환도 하면서, BFS로 점수 탐색도 해줘야 한다.

각각에 해당하는 함수와 Main에 해당하는 수도 코드를 작성해준다.

 

# ---------- Main ----------
# UP, RGT, DN, LFT
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
    
# UP, RGT, DN, LFT, dir = [0, 1, 2, 3]
cur_dir = 1

answer = 0
x, y = 0, 0
dice_map = [2, 4, 1, 3, 5, 6]

Main에서 우선 여러 잡다한 변수들을 선언해준다.

BFS에서 탐색에서 사용할 dx, dy 방향 변수를 선언해준다.

현재 방향을 상 우 하 좌 순서대로 0 1 2 3으로 선언한다. 이때 0123 순서는 dx, dy와 같게 한다.

또한 정답을 담을 answer, 현재 주사위 위치를 나타낼 x, y 변수도 선언한다.

마지막으로 현재 주사위 전개도를 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 적은 list를 선언한다.

 

# ---------- Function ----------
def check_range():
    global cur_dir, x, y

    if x < 0 or x >= row:
        cur_dir = (cur_dir + 2) % 4
        x += dx[cur_dir] * 2

    if y < 0 or y >= col:
        cur_dir = (cur_dir + 2) % 4
        y += dy[cur_dir] * 2

범위를 바로잡아주는 check_range()부터 하나씩 구현해보자.

x와 y 각각에 대해서 0보다 작고 row와 col보다 크거나 같은지 확인한다.

만약 범위를 벗어났다면, 방향을 반대로 바꿔주고, 바꾼 방향으로 2칸 움직인다.

이렇게 구현한 이유는 check_range()를 실제로 움직인 다음에 검사하기 때문이다.

 

예를 들어 (0, 0)에서 왼쪽으로 한 칸 간 (0, -1)이라고 가정해보자.

그럼 방향을 오른쪽으로 바꿔주고((cur_dir + 2) % 4), 2칸 이동해야 한다.

위에서 이미 1칸을 범위 밖으로 이동했기 때문이다.

 

(cur + 2) % 4가 반대 방향으로 가는 이유는 %는 나머지 연산, 즉 MOD 연산이기 때문이다.

방향은 0, 1, 2, 3 중에 하나이다. 이는 4의 나머지들로만 이루어져있다.

따라서 2칸 이동하고 4로 나눈 나머지라는 건, 0 -> 2, 1-> 3, 2-> 0, 3 -> 1로 바뀐다는 것이다.

 

# ---------- Function ----------
def roll_dice(dir: int) -> list:
    new_map = [0] * 6

    if dir == 0:
        new_map[0] = dice_map[2]; new_map[1] = dice_map[1]; new_map[2] = dice_map[4]
        new_map[3] = dice_map[3]; new_map[4] = dice_map[5]; new_map[5] = dice_map[0]
        return new_map

    elif dir == 1:
        new_map[0] = dice_map[0]; new_map[1] = dice_map[5]; new_map[2] = dice_map[1]
        new_map[3] = dice_map[2]; new_map[4] = dice_map[4]; new_map[5] = dice_map[3]
        return new_map

    elif dir == 2:
        new_map[0] = dice_map[5]; new_map[1] = dice_map[1]; new_map[2] = dice_map[0]
        new_map[3] = dice_map[3]; new_map[4] = dice_map[2]; new_map[5] = dice_map[4]
        return new_map

    else:
        new_map[0] = dice_map[0]; new_map[1] = dice_map[2]; new_map[2] = dice_map[3]
        new_map[3] = dice_map[5]; new_map[4] = dice_map[4]; new_map[5] = dice_map[1]
        return new_map

주사위 전개도를 바꾸는 roll_dice() 함수이다.

이부분에서는 규칙을 찾으려고 했으나, 하드 코딩으로 짜는 게 오히려 직관적이라 생각했다.

실제로 S-DES라고 DES를 간단하게(Simple) 만든 버전이 있다.

이때 값을 바꿔주는 Permutation(치환) 알고리즘 부분이 존재한다.

보통 S-DES는 6bit에서 10bit로 치환 부분은 하드 코딩해준다. 거기서 착안하여 이 부분은 하드코딩 해주었다.

위에 값이 어떻게 바뀌는지는 직접 주사위를 굴려가면서 확인해보자.

 

# ---------- Function ----------
def change_direction(dir: int, dice_num: int, map_num: int) -> int:
    if dice_num == map_num:
        return dir

    elif dice_num > map_num:
        dir += 1; dir %= 4
        return dir

    else:
        dir -= 1; dir %= 4
        return dir

방향을 바꾸는 change_direction() 함수이다. 이 함수는 생각보다 간단하다.

같다면 방향(dir)을 그대로 return하고, 주사위가 크다면 +1, 작다면 -1을 하고 return한다.

이때 %가 MOD 연산 결과가 들어간다는 것만 알면 간단하게 구현할 수 있다.

 

# ---------- Import ----------
from collections import deque

# ---------- Function ----------
def BFS(x: int, y: int, value: int) -> int:
    total = value
    visited = [[0] * col for _ in range(row)]

    queue = deque([(x, y)])
    visited[x][y] = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < row and 0 <= ny < col and visited[nx][ny] == 0 and graph[nx][ny] == value:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    total += value

    return total

이제껏 DFS와 BFS에 대한 그래프 문제를 착실히 풀어왔다면, 이만큼 쉬운 것 없을 것이다.

deque로 방문 여부(visited)를 확인하면서 지도 값(value)와 같은 부분을 전부 탐색한다.

BFS에서 한 가지 주의할 점은 visited[nx][ny] = 1 부분을 if문에서 셀 때, 바꿔주자는 것이다.

그렇지 않고 x, y = queue.popleft()에서 세준다면, 중복 탐색의 경우가 생겨 TLE나 MLE가 뜰 수 있다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Main ----------
for _ in range(move):    
    # Move
    x += dx[cur_dir]
    y += dy[cur_dir]
    
    # Check bound of range
    check_range()
    
    # Rolling dice
    dice_map = roll_dice(cur_dir)
    
    # Add score
    answer += BFS(x, y, graph[x][y])
    
    # Check direction change
    cur_dir = change_direction(cur_dir, dice_map[-1], graph[x][y])
    
print(answer)

위에서 작성한 함수들을 대단결할 차례이다.

현재 이동 방향(cur_dir)에 따라 이동해주고, 범위을 벗어났는지 확인(check_range())한다.

주사위가 굴러가고(roll_dice()) 점수 계산(BFS())을 한다.

마지막으로 방향을 바꿔주는(change_direction()) 과정을 이동 횟수(move)만큼 반복한다.

 

다행히도 이번 문제도 첫 시도만에 AC를 받았다.

하지만... 문제를 해석하고 이해하는데는데 거의 1시간을 투자했다.

평소 이해력과 문해력이 높으면 높았지 낮다고 생각하는 경우는 드물었는데 흠...

오히려 너무 많은 경우를 생각하는 것이 독이 된 것 같다는 느낌을 받았다.

적당한 선에서 너무 말도 안 되는 경우는 알아서 잘 걸러서 생각해야겠다.