[백준/Python] 15686 치킨 배달

문제는 여기

코드

import sys
from collections import deque
import itertools
input = sys.stdin.readline

n,m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
home_queue = deque()
result = []
queue = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1: # 집
            home_queue.append((i,j))
        elif graph[i][j] == 2: # 치킨집
            queue.append([i,j])

def chicken_distance(items):
    min_scores = []

    for home in home_queue: #집의 좌표
        min_score = 51
        for chicken in items:  # 치킨 집 좌표
            min_score = min(min_score, abs(chicken[0] - home[0]) + abs(chicken[1] - home[1]))
        min_scores.append(min_score)
    return sum(min_scores)

for item in list(itertools.combinations(queue, m)):
    result.append(chicken_distance(item))
    
print(min(result))

기록할 점

• 문제보고 백트래킹으로 풀면 된다는걸 알았으나 조합 구현이 잘 안돼서 itertools를 사용했다
  예를 들어 [(1,2),(2,2),(4,4)][(2,2),(1,2),(4,4)] 둘은 같은 걸로 취급되어야 하는데
  그 처리를 어떻게 하는지 한참 헤맸다
  
• 치킨 집 좌표를 미리 뽑아두고 idx도 기록해둔 뒤 그 다음 번의 좌표부터 방문하면 된다

visited = [0] * len(chicken)
for i in range(idx,len(chicken)):
    if not visited[i]:
       visited[i] = True
       dfs(i+1,cnt+1)
       visited[i]=False

오랜만에 1트 성공 🥳