피자 배달 거리 (DFS)
생성일: 2022년 2월 20일 오후 8:48
구현 코드
# 피자 배달 거리 (DFS)
import sys
from itertools import combinations
sys.stdin = open("input.txt", "rt")
def minDis(p, x, y):
min = 2147000000
for store in p:
dis = abs(store[0]-x) + abs(store[1]-y)
if dis < min:
min = dis
return min
if __name__ == "__main__":
n, m = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
pizza = []
for i in range(n):
for j in range(n):
if board[i][j] == 2:
pizza.append((i,j))
c = list(combinations(pizza, m))
res = []
for p in c:
tot = 0
for i in range(n):
for j in range(n):
if board[i][j] == 1:
tot += minDis(p, i, j)
res.append(tot)
print(min(res))
모범 답안
import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
global res
if L==m:
sum=0
for j in range(len(hs)):
x1=hs[j][0]
y1=hs[j][1]
dis=2147000000
for x in cb:
x2=pz[x][0]
y2=pz[x][1]
dis=min(dis, abs(x1-x2)+abs(y1-y2))
sum+=dis
if sum<res:
res=sum
else:
for i in range(s, len(pz)):
cb[L]=i
DFS(L+1, i+1)
if __name__=="__main__":
n, m=map(int, input().split())
board=[list(map(int, input().split())) for _ in range(n)]
hs=[]
pz=[]
cb=[0]*m
res=2147000000
for i in range(n):
for j in range(n):
if board[i][j]==1:
hs.append((i, j))
elif board[i][j]==2:
pz.append((i, j))
DFS(0, 0)
print(res)
차이점
- 내가 구현한 코드에서는 피자 가게들의 조합을 파이썬의 itertools의 combinations을 import하여 편리하게 구하였다. (실전에서 해당 패키지를 사용하지 못할 수도 있기 때문에 직접 DFS로 조합을 구하는 방법 또한 숙지해야 한다.)
- 모범 답안에서는 피자 가게의 좌표 뿐만아니라 집들의 좌표도 리스트에 저장하여 이중 for문을 한번만 돌아도 문제를 풀 수 있도록 짜여져있다.
Author And Source
이 문제에 관하여(피자 배달 거리 (DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/피자-배달-거리-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)