[Baekjoon 15686] 치킨 배달

문제

💛Ⅴ [Baekjoon 15686 - 치킨 배달]

문제 풀이 방법

처음 문제를 읽고 각 집에서 치킨집까지의 최단거리를 구하는 bfs문제라고 생각하고 접근하였지만 시간초과가 났다. 시간을 줄이기 위해서 처음부터 다시 생각을 해보니 집과 치킨집과의 거리를 계산하기 위해서는 각 좌표값만 알면 계산할 수 있었다. 그래서 이 문제는 전체 모든 경우를 검사하는 완전탐색으로 풀 수 있었다.

1. 도시의 정보를 입력받으면서 치킨집과 집의 좌표를 저장한다.
2. 치킨집 중 m개의 치킨집만 선택한다.
   1. 각 집을 순회하면서 치킨집까지의 최소거리를 chicken_distance에 축적한다.
   2. chicken_distance 중에서 최솟값을 출력한다.

풀이 코드

Python

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

N, M = map(int, input().split())
graph = []
chickens = []
houses = []
answer = []
for i in range(N):
    tmp = list(map(int, input().split()))
    graph.append(tmp)
    for j, x in enumerate(tmp):
        if x == 1: # 집의 좌표값 저장
            houses.append((i,j))
        if x == 2: # 치킨집이라면 좌표값 저장
            chickens.append((i,j))

for chicken in list(combinations(chickens, M)):
    chicken_distance = 0
    distance = []
    for house in houses:
        distance = [abs(house[0] - i) + abs(house[1] - j) for i,j in chicken]
        chicken_distance += min(distance)
    answer.append(chicken_distance)

print(min(answer))