[백준 22949] 회전 미로 탐색

22949번: 회전 미로 탐색

(내가 만든 문제라 해설이 길다... 다른 문제는 간단히 쓸 예정...)

 

내가 만든 문제이다. 배열 돌리기와 미로 탐색을 적절히 섞으면 적당한 난이도가 나올 것이라 생각하고 만들었지만 실제 찍힌 티어는 골드 1 ~ 플레 5 정도였고, 지금까지 푼 사람이 8명 밖에 없다...

 

지문 쓰는 능력이 그렇게 좋은 편(사실, 아직도 좋은 편이 아닌거 같다)이 아니여서 행렬에서 4x4 크기의 정사각형들로 나누는 것을 수식으로 표현해서 그런지 많은 분들이 풀지 않거나 푸는데 어려움을 겪은 것 같다....

 

예를 들어 아래와 같이 16x16 행렬이 있다고 해보자.

가로가 16, 세로가 16인 행렬

지문에 있는 $\{(y, x) | 4×i < y ≤ 4×(i+1), 4×j < x ≤ 4×(j+1), (0 ≤ i, j < k)\}$ 이를 만족하는 구역은 총 16가지가 나온다. 아래 그림이 각 구역을 나눈 것이다.

16x16 행렬을 각 구역(크기 : 4x4)으로 나눈 결과

지문에 설명이 되어 있지만 중요한 사실을 다시 정리해보겠다. (지문에서 혼란이 올 수 있는 단어도 존재하긴 한다...)

 

 - 현재 있는 위치가 포함된 구간만 시계방향 90도로 회전한다. 예를 들어, 현재 (3, 2)에 있다면 구역 1만 시계방향으로 90도 회전한다. 이때, 나머지 구역들은 처음 주어진 상태로 돌아간다.

 - 각 시간마다 5가지 행동 중 하나를 할 수 있다. (상하좌우 중 하나로 이동하기, 정지하기)

 - 행동을 하고 난 후 행렬이 회전한다.

 - 구하고자 하는 것은 미로를 탈출하기까지 최소 시간을 구하는 것이다. (지문에는 최소 이동시간으로 되어있지만 정확히 따지고 보면 이동시간보다 탈출까지 지난 시간을 의미한다.)

 - 미로를 탈출 할 수 없을 수도 있다.

 

간단하게 문제 리뷰를 했으니 어떻게 풀어야 하는지 정리해보자. 여러가지 떠오르는게 있겠지만 대표적으로 3가지에 대해 정리하겠다.

 

1. 미로탐색에 배열 돌리기만 추가 되긴 했지만 방문 체크를 어떻게 해야할까?

2. 어떤 자료구조, 알고리즘을 써야할까?

3. 시간복잡도는 어떻게 될까? 제한시간 안에 해결할 수 있나?

 

---

먼저 1번을 보면 매 시간마다 항상 구역들 중 한 곳이 회전하기 때문에 상태가 항상 같은 것은 아니다. 상태가 나올 수 있는 경우의 수를 한번 구해보자.

 

각 구역이 총 4번 회전하면 원래 상태랑 같기 때문에 각 구역당 4가지 상태가 존재하고 가로, 세로의 길이가 4$k$라고 가정하면 구역의 개수는 $k×k$가 된다. $k$의 최대 값은 125이기 때문에 상태의 가짓수는 15,625 가지이다. 각 상태의 배열을 저장한다고 하면 [상태][row][col]와 같이 저장을 하면 된다. 행렬의 크기는 $4k×4k$이고 int 타입으로 선언한다고 가정해보면 15,625×500×500×4 Byte = 15.625 GB(1M = 1024 기준 14.552 GB)를 먹는다. 메모리 제한인 1 GB를 훨씬 넘는다.

 

그러면 어떻게 해야 메모리를 줄일 수 있을까 ?

 

여러가지 상태가 나오는 이유는 하나의 구역이 회전하기 때문이다. 그런데 처음 주어진 상태에서 하나의 구역만 회전한 상태만 나오기 때문에 [하나의 구역이 회전한 횟수][row][col]로 저장하면 된다. 이때 하나의 구역이 회전한 횟수는 시계방향으로 4번 돌면 원래상태로 돌아오기 때문에 최대값은 4가 된다. 따라서 메모리를 계산해보면 4×500×500×4 Byte = 4 MB (1M = 1024 기준 3.815 MB) 밖에 안먹는 것을 알 수 있다.

---

두 번째로 어떤 자료구조, 알고리즘을 써야하는지 생각해보자. 그 전에 어떤 로직이 필요한지 정리해보자.

 

- 각 구역을 시계방향으로 회전하는 Rotate 함수

- 시작점에서 출발하여 도착점으로 가는데 걸리는 최소시간

 

크게 나눠보면 위와 같이 2가지가 있다. 첫 번째 로직은 배열 돌리기3에서 3번 연산처럼 구현으로 할 수 있다.

두 번째는 하나의 구역이 시계방향으로 회전하고 다른 구역으로 이동할 때 회전했던 구역은 원래대로 돌아가기 때문에 미로 탐색처럼 BFS를 이용해서 풀 수 있다.

---

마지막으로 시간복잡도는 어떻게 나오는지 계산해보자. (지금 와서 하는 말이지만, 실제 문제 풀 때와 다르다.)

위에서 시간이 가장 오래걸리는 로직은 미로 탐색을 하는 로직이다. 이를 구하는 방법은 정점 최대 방문 횟수를 구하면 된다. 해당 문제에서 각 정점은 각 상태로 볼 수 있어서 위에서 정리한 방문상태 [하나의 구역이 회전한 횟수][row][col]가 각 정점으로 보면 된다.

이를 최대로 방문하는 것은 모든 정점을 방문하면 되는것이므로 시간복잡도는 $O(4NM) = O(NM)$이 된다.

 

 

---

하나의 팁을 알려주자면 해당 문제에서 상하좌우로 이동하거나 가만히 있을때 매번 각 구역을 회전할 필요가 없다. 하나의 구역을 회전하는데 필요한 연산은 상수값인 약 16이 들지만 이를 미리 다 구해놓으면 미로탐색할때 다음 구역을 O(1)로 이동할 수 있다.

 

from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

def region(y, x, k):
    y, x = y // 4 * 4, x // 4 * 4
    return y * k + x

def inrange(y, x, N):
    return 0 <= y and y < N and 0 <= x and x < N

def next_pos(y, x):
    by, bx = y // 4 * 4, x // 4 * 4
    y, x = y % 4, x % 4
    return x + by, 3 - y + bx

# Constant
Dy = (-1,1,0,0)
Dx = (0,0,-1,1)

K = int(input())
N = 4*K
Map = [list(input()) for i in range(N)]
Rotate_Map = [[['.' for j in range(N)] for i in range(N)] for k in range(4)]
dist = [[[-1 for j in range(N)] for i in range(N)] for k in range(4)]
start_point, end_point = (0, 0), (0, 0)

for i in range(N):
    for j in range(N):
        if Map[i][j] == 'S':
            start_point = (i, j)
            Map[i][j] = '.'
        if Map[i][j] == 'E':
            end_point = (i, j)
            Map[i][j] = '.'

for regiony in range(K):
    for regionx in range(K):
        y, x = regiony * 4, regionx * 4
        tmp = []
        for h in range(4): tmp.append(Map[y + h][x:x+4])
        for cnt in range(4):
            for hy in range(4):
                for hx in range(4):
                    Rotate_Map[cnt][y + hy][x + hx] = tmp[hy][hx]
            tmp = [list(line) for line in list(zip(*tmp[::-1]))]

# BFS (미로탐색)
Q = deque([(0, *start_point)])
sy, sx = start_point
dist[0][sy][sx] = 0
while Q:
    turn, y, x = Q.popleft()
    current_region = region(y, x, K)

    # Move U, D, L, R
    for dy, dx in zip(Dy, Dx):
        qy, qx = dy + y, dx + x
        next_region = region(qy, qx, K)
        if not inrange(qy, qx, N): continue
        if next_region == current_region:
            if Rotate_Map[turn][qy][qx] == '#': continue
            qy, qx = next_pos(qy, qx)
            next_turn = (turn + 1) % 4
            if dist[next_turn][qy][qx] != -1: continue
            dist[next_turn][qy][qx] = dist[turn][y][x] + 1
            Q.append((next_turn, qy, qx))
        else:
            if Rotate_Map[0][qy][qx] == '#': continue
            qy, qx = next_pos(qy, qx)
            if dist[1][qy][qx] != -1: continue
            dist[1][qy][qx] = dist[turn][y][x] + 1
            Q.append((1, qy, qx))
    
    # Stay
    next_turn, qy, qx = (turn + 1) % 4, y, x
    qy, qx = next_pos(qy, qx)
    if dist[next_turn][qy][qx] == -1:
        dist[next_turn][qy][qx] = dist[turn][y][x] + 1
        Q.append((next_turn, qy, qx))

ans = -1
y, x = end_point
for k in range(4):
    value = dist[k][y][x]
    y, x = next_pos(y, x)
    if value == -1: continue
    if ans == -1: ans = value
    elif ans > value: ans = value

print(ans)