[백준 23354] 군탈체포조

문제

군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다.

어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 주어졌는데, 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비를 최대한 아끼면서 탈영병을 모두 잡으려고 한다.

지도는 N * N 크기의 격자로 표현된다. 지도 위에는 부대와 탈영병들의 위치가 주어지며 부대나 탈영병이 없는 나머지 칸에는 모두 톨게이트가 존재한다. 

각 톨게이트에는 내야 하는 통행료가 정해져 있고 톨게이트가 있는 칸을 방문하기 위해서는 반드시 통행료를 지불해야 한다. 또한 같은 칸을 여러 번 방문해도 매번 통행료를 내야 한다.

호열이는 부대에서 출발해 탈영병을 모두 잡은 후 복귀해야하며, 중간에 부대를 들려도 상관없다. 단, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있고 지도에 표시된 곳 이외의 공간에는 갈 수 없다.

아무것도 하기 싫은 호열이를 위해 부대에서 출발해 탈영병을 모두 잡은 후 부대로 복귀하는데 드는 최소 비용을 대신 구해주자.

입력

첫째 줄에 격자의 크기 N이 주어진다. (5 ≤ N ≤ 1,000)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. −1은 부대, 0은 탈영병, 1이상의 정수는 톨게이트의 통행료를 의미하며 모든 통행료는 1,000 이하의 정수이다.

단, 입력에서 부대는 1개만 주어지며 탈영병의 수는 5명 이하로 주어진다.

탈영병이 존재하지 않을 수도 있다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

---

풀이

먼저 탈영병의 위치들을 기점으로 다른 좌표까지의 최소 비용들을 구하고 저장해준다

그 이후 어떻게 모든 탈영병을 잡는 최단거리를 결정할지 고민 한 결과 탈영병의 수가 5명 이하인 문장을 보고 모든 경우를 비교해보기로 했다

 

간단하게 정리하자면,

1. 부대 위치와 탈영병들의 위치 저장

2. 저장된 부대 위치와 탈영병들의 위치를 중심으로 하는 최소비용 맵을 저장 (다익스트라)

3. 부대 - (n명의 탈영병 위치 순열) - 부대 이동 비용을 모든 경우 비교하여 최솟값 도출

 

N = int(input())
costMap = []
deserters = []  # 탈영병 위치
distances = {} # 탈영병의 위치로부터 최단거리들
ans = INF

for y in range(N):
    line = list(map(int,input().split()))
    for x in range(N):
        if line[x] == -1:   # 부대 위치 저장
            home = (y,x)
        elif line[x] == 0:  # 탈영병 위치 저장
            deserters.append((y,x))
    costMap.append(line)

costMap[home[0]][home[1]] = 0   # 부대 cost 0으로 변경

 

먼저 탈영병과 부대 위치를 저장하고 이후 최소비용 계산을 위해 부대 cost를 0으로 바꿔주었다

 

 

nx = [0,1,0,-1]
ny = [-1,0,1,0]

# 시작 위치를 기준으로 최단거리 맵 반환
def dijkstra(start):
    sy,sx = start
    distance = [[INF for _ in range(N)] for _ in range(N)]
    distance[sy][sx] = 0
    Q = []
    heappush(Q,[0,start])

    while Q:
        nowCost, nowNode = heappop(Q)
        y,x = nowNode
        if distance[y][x] < nowCost:
            continue
        for idx in range(4):
            nextX = x + nx[idx]
            nextY = y + ny[idx]
            if 0 <= nextX and nextX < N and 0 <= nextY and nextY < N:
                if nowCost+costMap[nextY][nextX] < distance[nextY][nextX]:
                    distance[nextY][nextX] = nowCost+costMap[nextY][nextX]
                    heappush(Q,[nowCost+costMap[nextY][nextX],(nextY,nextX)])
    return distance

 

우선순위 큐와 사방 탐색을 사용하여 시작 좌표를 중심으로 다른 좌표까지의 최소비용 맵을 반환

 

 

distances[home] = dijkstra(home)    # 부대에서부터의 최단거리
for node in deserters:
    distances[node] = dijkstra(node)    # 각 탈영병으로부터의 최단거리

 

이렇게 구현하면 시간초과가 나지 않을까 의심했지만 최대 6개의 최소비용 맵을 딕셔너리에 저장하였다

이 과정에서 key를 부대,탈영병의 위치 좌표로 두었다

 

 

per = permutations(deserters,len(deserters))    # 탈영병 위치를 순열로 모든 경우를 저장

for course in list(per):
    groupCost = 0
    current = home  # 시작 위치는 부대
    for node in course:
        y,x = node
        groupCost += (distances[current])[y][x] # 탈영병 위치로 이동 및 이동비용++
        current = node  # 이동한 탈영병 위치로 기준 변경
    y,x = home
    groupCost += (distances[current])[y][x] # 마지막 탈영병 위치에서 부대 북귀 비용++
    if groupCost < ans:
        ans = groupCost

print(ans)

 

순열로 잡을 탈영병들의 순서를 모두 고려해주었다

부대 - 탈영병들 - 부대 순으로 최소 비용을 계산해주고 그 과정에서 최소 비용을 구했다