[백준/파이썬] 15686번: 치킨 배달

문제

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

풀이

• 도시의 크기: N×N
  • 0: 빈 칸
  • 1: 집
  • 2: 치킨집
• 치킨 거리: 가장 가까운 치킨집과의 거리(맨해튼 거리)
• 모든 집의 치킨 거리를 더한 값(도시의 치킨 거리) 중 최솟값 출력

치킨집 후보 중에서 M개를 고르는 조합을 구한 후, 각 조합마다 치킨 거리를 계산해서 최솟값을 갱신하면 됩니다.

    h = [] # 집 위치
    ch = [] # 치킨집 위치
    
    # 위치 탐색
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                h.append((i,j))
            elif graph[i][j] == 2:
                ch.append((i,j))

탐색에 진행할 집과 치킨집의 좌표를 각 배열에 저장

def distance(chicken):
    total = 0
    for x1,y1 in h: # 모든 집 좌표
        dist = 1e9
        for x2,y2 in chicken: # 선택한 치킨집과의 거리 계산
            dist = min(dist, abs(x1-x2) + abs(y1-y2))
        total += dist
    return total

치킨 거리를 구하는 함수
치킨 거리의 누적합을 return

def dfs(s,d):
    global answer
    if d == m:
        dist = distance(chicken) # 현재 선택한 조합으로 치킨거리 계산
        answer = min(answer, dist) # 최솟값 갱신
        return
    
    for i in range(s, len(ch)): # 현재 인덱스부터
        chicken.append(ch[i]) # 치킨집 선택
        dfs(i+1, d+1) # 다음 치킨집 탐색
        chicken.pop()

s번 인덱스부터 시작, d개 선택
d가 M개가 됐을 때마다 도시 치킨 거리 계산

    answer = 1e9
    chicken = [] # 선택된 치킨집 조합
    
    dfs(0,0) # 0번 인덱스부터 시작
    print(answer)

ch 중에 M개를 뽑아 치킨 거리 최솟값 계산하면 끝

코드

import sys
input = sys.stdin.readline

def distance(chicken):
    total = 0
    for x1,y1 in h:
        dist = 1e9
        for x2,y2 in chicken:
            dist = min(dist, abs(x1-x2) + abs(y1-y2))
        total += dist
    return total

def dfs(s,d):
    global answer
    if d == m:
        dist = distance(chicken)
        answer = min(answer, dist)
        return
    
    for i in range(s, len(ch)):
        chicken.append(ch[i])
        dfs(i+1, d+1)
        chicken.pop()

if __name__ == "__main__":
    n,m = map(int,input().split())
    graph = [list(map(int,input().split())) for _ in range(n)]
    
    h = []
    ch = []
    
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                h.append((i,j))
            elif graph[i][j] == 2:
                ch.append((i,j))
                
    answer = 1e9
    chicken = []
    
    dfs(0,0)
    print(answer)