Koala - 9기/코딩테스트 준비 스터디

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

beans3142 2023. 2. 19. 08:20

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

 

23354번: 군탈체포조

군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라

www.acmicpc.net

문제 분석

난이도

골드3

분류

다익스트라, 브루트포스

들어가기 전에

제 1회 KAUPC 출제 문제

문제

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

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

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

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

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

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

입력

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

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

단, 입력에서 부대는 1개만 주어지며 탈영병의 수는 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)

후기