백준 28215번 대피소 - Python

문제

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

---

문제 해석

입력

첫 번째 줄에 집의 수 N, 대피소의 수 K가 입력된다.
그 뒤 집들의 좌표가 N줄에 걸쳐 입력된다.

출력

입력 받은 집의 좌표 중에서 K개의 대피소를 선정한다.
선정할 수 있는 모든 경우의 수 중에서 대피소에서 집 까지의 거리 중 가장 긴 값이 가장 작을 때의 최장거리를 출력한다.
여기서 대피소 까지의 거리란
(대피소의 X좌표) - (집의 X좌표) 의 절대값과 (대피소의 Y좌표) - (집의 Y좌표) 의 절대값을 합한 값을 의미한다.

---

풀이

1번 풀이

브루트포스 알고리즘을 이용한다.
집들 중에서 대피소를 선정하는 과정은 '조합'을 활용한다.
but. 대피소의 수가 정해져있지 않으므로 직접 구현하기보다는 라이브러리를 사용한다.
itertools 라이브러리의 combination을 이용해 조합 리스트를 구한다.
구한 리스트로 for문을 돌며 대피소가 어떤 집에 있어야 최단거리로 모든 집이 접근할 수 있는지 확인한다.
for문을 모두 돈 후에 최소값을 출력한다.

from itertools import combinations

N, K = map(int, input().split())
H = [list(map(int, input().split())) for _ in range(N)]

Min_Range = float('inf')

for S in combinations(range(N), K):
    Max_Range = 0

    for i in range(N):
        Home = H[i]
        Shelter = [H[S[a]] for a in range(K)]
        min_Range = float('inf')

        for j in Shelter:
            Range = abs(Home[0] - j[0]) + abs(Home[1] - j[1])
            min_Range = min(min_Range, Range)

        Max_Range = max(Max_Range, min_Range)

    Min_Range = min(Min_Range, Max_Range)

print(Min_Range)

---

새롭게 배운 것

1. itertools 라이브러리

조합 뿐만 아니라 리스트 무한 반복, 누적합, 순열 등 다양한 기능이 있고, 이 코드에서 사용한 것처럼 주로 반복문에서 많이 사용될 것 같다.

2. 무한대

float('inf')로 무한대를 지정할 수 있다.
출력했을 때 'inf'라 나오고 최소값을 구할 때 안전하게 사용할 수 있겠다.