15686

날짜 : 2023. 05. 04

사용 언어 : python

 

문제

 

 

코드

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
graph = list()
house = list()  # 집의 좌표
chicken = list()  # 치킨집 좌표

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
for i in range(n): # 최대 2500
    for j in range(n):
        if graph[i][j] == 1:
            house.append([i, j])
        elif graph[i][j] == 2:
            chicken.append([i, j])

res = int(1e9)  # 도시의 치킨거리
for pick in combinations(chicken, m):  # 모든 치킨집 중에서 m개 뽑은 케이스 -> 최대 13C5 * 
    temp = 0
    for h in house:
        d = 10000  # 하나의 가구의 치킨거리
        for p in pick:
            d = min(d, abs(h[0]-p[0]) + abs(h[1]-p[1]))
        temp += d
    res = min(res, temp)
print(res)

 

 

풀이

- 치킨집, 가정집의 좌표를 각 리스트에 저장

- combinations를 활용해 전체 치킨집 중에서 m 개를 추출 -> pick

- 하나의 가정집을 토대로 pick한 치킨집에 대한 최소 치킨거리를 구한다.(하나의 가구 대한 치킨거리)

- 이를 temp 에 더한 후 모든 가정집에 대한 치킨거리 총합이 구해졌다면 이 값을 토대로 도시의 치킨거리의 최소값을 최신화한다.

 

 

알게된 점

- 시간복잡도를 고려해서 BFS로 구해볼까 했는데 너무 복잡해져서 다른사람의 풀이를 참고했고, combination으로 풀이하는 것을 알게 되었다.

- combination으로 m개를 뽑은 케이스를 만들면 이 케이스를 토대로 도시의 치킨거리를 구할 수 있다.

- 그리고 이 치킨거리를 모든 경우의수를 비교하면서 최소값으로 갱신하는 원리였다.

- 풀이 이후 시간복잡도를 구해보았는데 각각 2 ≤ N ≤ 50, 1 ≤ M ≤ 13 이었기 때문에 이중 for문에서는 50*50 = 2500, 3중 for문에선 O(13C6*2N*13) < 100,000,000 이었다. 그래서 combination을 활용한 브루트포스가 가능했던 것 같다.

 

 

 

참고 사이트

- https://codesyun.tistory.com/185

[BOJ / 백준] 15686번 치킨 배달 파이썬(Python) 문제 풀이