병원 거리 최소화하기

지금 보는 과거 코테는 정말 쉬웠네요.

ㅠㅠㅠㅠ물론 정형화되고 많은 해설과 풀이 덕분이지만... 진짜 이러다 몇년 후에는 이번에는 다행스럽게도 다이아 문제는 안나오고 플레문제만 제출됐어요! 하는게 아닐까하는.....걱정이 생겼어요.

근데 이런 쉬운 문제도 한번 틀려버린 나는...

1. 실패 -> 병원기준으로 하다보니 헷갈려서 연산 자체가 틀렸어요.

병원기준 -> 사람기준

from itertools import combinations
import heapq
# 3 1
# 0 1 0
# 0 2 2
# 0 1 0

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

h = []
p = []
for y in range(n):
    for x in range(n):
        if graph[y][x] == 2:
            h.append((y,x))
        elif graph[y][x] == 1:
            p.append((y,x))


answer = 1000000000
for i in combinations(h, m): #모든 경우의 수
    total_distance = 0
    for y, x in i: # combi 일부분
        tmp_mindistance = 10000000
        for py, px in p: #사람 위치
            distance = abs(y - py) + abs(x - px)
            tmp_mindistance = min(tmp_mindistance, distance)
        tmp_mindistance += min(distance, tmp_mindistance)
    total_distance += tmp_mindistance
    answer = min(total_distance, answer)
print(answer)

 

2. 성공

from itertools import combinations
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

h = []
p = []
for y in range(n):
    for x in range(n):
        if graph[y][x] == 2:
            h.append((y,x))
        elif graph[y][x] == 1:
            p.append((y,x))

answer = 1000000000
for i in combinations(h, m): #모든 경우의 수
    total_distance = 0
    for py, px in p: #사람 기준으로 
        p_h_distance = 10000000
        for y, x in i: # 가장 가까운 병원 위치를 찾음
            distance = abs(y - py) + abs(x - px)
            p_h_distance = min(distance, p_h_distance)
        total_distance += p_h_distance #total 에 더해줌
    answer = min(total_distance, answer)
print(answer)