[파이썬/python] 백준 - 25585 86 ─에이티식스─ 1

문제

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

---

문제 설명

1. 대각선 네 방향으로 이동이 가능한 저거노트와 레기온이 2차원 배열로 주어진다.
   1. 빈 공간 : 0, 저거노트 : 1, 레기온 : 2
   2. 저거노트의 현재 위치가 (r,c)라면 (r-1, c-1), (r-1, c+1), (r+1, c-1), (r+1, c+1)로 이동이 가능하다.
2. 저거노트가 모든 레기온을 해치우는데 걸리는 최소 시간을 계산한다.

 

---

풀이

처음에는 DFS로 푸는 문제라고 생각해서 꽤 오랜 시간 동안 삽질을 했다.

 

문제의 배열 크기가 100×100이기 때문에 단순히 DFS로 풀이하게 되면 탐색 가능한 위치가 약 5000개 정도가 된다. 이 모든 위치를 탐색한다고 가정하면 경우의 수는 대략 5000! 수준이 되는데, 이는 현실적으로 불가능한 시간복잡도이다. 처음부터 시간복잡도를 계산해보고 접근했다면 시간을 조금 더 아낄 수 있었을 텐데 아쉽다.

 

문제를 다시 읽어보면 레기온의 개수는 최대 10개라는 문장이 있다. 따라서 전체 맵을 탐색하는 방식이 아니라, 저거노트와 각 레기온 사이의 거리를 계산하는 방식으로 문제를 풀 수 있다.

 

레기온의 최대 개수가 10개이므로, 순서를 모두 고려한다고 해도 경우의 수는 10! 정도이다. 이는 약 300만 정도의 연산이므로 충분히 계산 가능한 수준이다.

 

이제 각 레기온 사이의 거리를 구해야 하는데, 여기서 사용하는 거리 공식이 우리가 일반적으로 사용하던 것과는 조금 다르다. 보통 두 점 사이의 최소 거리를 구할 때는 맨해튼 거리 공식을 사용한다.

 

맨해튼 거리는 다음과 같이 계산한다.

 

abs(y2 - y1) + abs(x2 - x1)

 

하지만 이 문제에서는 상하좌우 이동이 불가능하고, 오직 대각선으로만 이동할 수 있다. 따라서 약간 변형된 방식으로 거리를 계산해야 한다.

 

예를 들어 (0,0)과 (3,3) 사이의 거리는 3이다. 단순히 대각선으로 세 번 이동하면 도착할 수 있기 때문이다.

 

또 다른 예로 (0,0)과 (4,0)을 생각해보자. 직선 이동이 불가능하기 때문에 바로 위로 올라갈 수는 없다. 대신 대각선으로 오른쪽으로 이동했다가 다시 왼쪽으로 이동하는 방식으로 접근해야 한다. 즉 오른쪽 방향으로 두 번, 왼쪽 방향으로 두 번 이동해야 해당 위치에 도달할 수 있다.

 

여기서 중요한 힌트를 얻을 수 있다. 대각선으로 이동하면 x와 y의 거리가 동시에 1씩 줄어든다. 따라서 dx와 dy 중 작은 값만큼 먼저 대각선으로 이동하고, 남은 거리만큼 반대 방향 대각선 이동을 통해 맞춰주면 된다.

 

말로만 설명하면 이해하기 어려울 수 있으니 간단한 예시를 들어보자.

 

(0,0)에서 (5,3)으로 이동한다고 가정하자.

 

먼저 대각선으로 이동하면서 (0,0) → (3,3)까지 이동한다. 이때 이동 횟수는 3이다.

 

이렇게 dx와 dy 중 작은 값만큼 이동하면 두 좌표가 (3,3)과 (5,3)처럼 한 축이 맞춰진 상태가 된다. 이제 남은 차이는 x좌표 2칸이다. 직선 이동이 불가능하기 때문에 대각선으로 한 번 오른쪽, 한 번 왼쪽으로 이동하면서 총 두 번 이동하면 (5,3)에 도달할 수 있다.

 

결국 이동 거리는

 

min(dx, dy) + |dx - dy|

 

가 된다. 이를 정리하면 결국 dx와 dy 중 더 큰 값이 최소 이동 거리라고 볼 수 있다.

 

탐색을 진행하기 전에 몇 가지 예외 상황을 먼저 확인할 필요가 있다.

 

첫 번째는 아예 도달할 수 없는 경우이다.

 

저거노트의 현재 위치를 (y, x)라고 하자. 대각선 이동은 y와 x가 동시에 ±1씩 변하기 때문에, 이동할 때마다 y + x 값의 홀짝성이 유지된다. 즉 현재 위치에서 y + x가 짝수라면 이후에 도달할 수 있는 위치도 모두 짝수이고, 홀수라면 이후 위치도 모두 홀수이다.

 

따라서 레기온의 위치와 홀짝성이 맞지 않는다면 그 위치에는 절대 도달할 수 없다. 이 경우는 시작하기 전에 불가능한 경우로 판단할 수 있다.

 

두 번째는 현재까지 구한 거리(dist)가 이미 구해둔 최소 거리(min_dist)보다 커지는 경우이다.

 

탐색을 진행하면서 현재 누적된 거리가 기존 최소 거리보다 커진다면 더 이상 탐색을 진행할 필요가 없다. 따라서 이 경우에는 바로 리턴하도록 가지치기를 해주었다.

 

이 두 가지 예외 처리를 적용한 뒤, 모든 레기온 사이의 거리를 계산하며 탐색을 진행했고 그중 최소 거리를 정답으로 출력했다.

---

코드

import sys
sys.setrecursionlimit(10**3)
input = sys.stdin.readline

INF = sys.maxsize
dy = [-1,-1,1,1]
dx = [-1,1,-1,1]

n = int(input())
board = [[0 for _ in range(n)]for _ in range(n)]

region = []
cnt = 0
for i in range(n):
    tmp = list(map(int,input().split()))

    for j in range(len(tmp)):
        if tmp[j] == 2:
            sy,sx = i,j
        elif tmp[j] == 1:
            region.append((i,j))
            cnt += 1
        board[i][j] = tmp[j]

mo = (sy+sx) % 2


for y,x in region:
    if (y + x) % 2 != mo:
        print("Shorei")
        exit()

def cal_dist(y1,x1,y2,x2):
    x_gap = abs(x2-x1)
    y_gap = abs(y2-y1)

    return max(x_gap, y_gap)


min_dist = INF
visited = [0 for _ in range(len(region))]
def solve(y, x, dist, depth):
    global min_dist
    if dist > min_dist:
        return
    
    if depth == len(region):
        min_dist = min(min_dist, dist)
        return
    
    for i in range(len(region)):
        if visited[i]:
            continue

        ny,nx = region[i]

        visited[i] = 1
        solve(ny,nx,dist + cal_dist(y,x,ny,nx), depth + 1)
        visited[i] = 0

solve(sy,sx, 0, 0)

print("Undertaker")
print(min_dist)

---

시간복잡도

• 최악의 경우 레기온의 개수는 10개이다. 즉 $10! = 3628800$ 정도의 연산이 필요하다.
• 따라서 $O(3*10^6)$ 정도의 시간복잡도를 가진다.