[백준 / Python] 23354 군탈체포조

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

23354번: 군탈체포조

문제 분석

난이도

골드3

분류

다익스트라, 브루트포스

들어가기 전에

제 1회 KAUPC 출제 문제

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

 

문제 풀이

 

풀이

탈영병의 수는 최대 5명이다. 그러므로 방문 순서의 경우의 수는 5! 정도이며 120개이다.

시작점과 각 탈영병의 위치에서 다익스트라를 돌려준 뒤 permutations을 통해 모든 경우에 대해 대입해주면 된다.

정점의 수는 1000*1000이고 간선의 수는 대략적으로 1000*1000*4이므로 대충 6백만 언저리 정도의 시간이 걸리고, 이것을 6번 정도 반복해야 하므로 시간이 상당히 오래걸린다.

따라서 쓸데없는 부분에서 시간을 잡아먹을 경우 TLE가 나올 수 있는 문제이다.

소스코드

from sys import stdin
from heapq import heappop,heappush
from itertools import permutations
from math import inf
input=stdin.readline

dx=[0,0,1,-1]
dy=[1,-1,0,0]

n=int(input())

arr=[list(map(int,input().split())) for i in range(n)]

tar=[]
boodae=[]

for i in range(n):
    for j in range(n):
        if arr[i][j]==0:
            tar.append([j,i])
        elif arr[i][j]==-1:
            boodae=[j,i]

arr[boodae[1]][boodae[0]]=0

def dijk(X,Y):
    v=[[inf]*n for i in range(n)]
    queue=[[0,X,Y]]
    while queue:
        dist,x,y=heappop(queue)
        if v[y][x]<dist:
            continue
        v[y][x]=dist
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if -1<nx<n and -1<ny<n:
                adist=dist+arr[ny][nx]
                if v[ny][nx]>adist:
                    v[ny][nx]=adist
                    heappush(queue,(adist,nx,ny))

    return v

each_dist=[dijk(boodae[0],boodae[1])]
for i in tar:
    each_dist.append(dijk(i[0],i[1]))

case=list(permutations([i for i in range(len(tar))],len(tar)))

ans=inf
for i in case:
    dist=0
    befx=boodae[0]
    befy=boodae[1]
    bef=0
    for j in range(len(i)):
        nowplace=tar[i[j]]
        nowx,nowy=nowplace[0],nowplace[1]
        dist+=each_dist[bef][nowy][nowx]
        befx=nowx
        befy=nowy
        bef=i[j]+1
    dist+=each_dist[bef][boodae[1]][boodae[0]]
    ans=min(ans,dist)

print(ans)

후기

직관적이고 재미있는 문제라고 생각한다.