백준 1090번 파이썬 문제풀이(체커)

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

1090번: 체커

---

백준 14400번 파이썬 (편의점 2)

과 비슷한 문제이나 난이도가 꽤있는 문제이다.

 

결국 문제에서 요하는 것은 완전탐색이다. N이 50이라 O(N^4)까지 돌 수 있어서 완전탐색으로 접근하면 생각보다 쉽게 해결할 수 있다. 

문제해결방식은 다음과같다.

 

1. 우선 모든 좌표의 조합을 돈다. (O(n^2))

2. 각각의 좌표마다 모든 좌표와의 거리를 구한다. 

3. 오름차순 정렬 후 1개부터~N개까지의 최소 거리를 구한다.

 

다음의 3가지 과정을 거치면서 O(N^3)으로 모든 점에 대해서 각각의 체스의 개수마다 최소 거리를 구할 수 있다.

자세한 내용은 주석처리 해놓았다.

arr = []
N = int(input())

for _ in range(N):
    arr.append(list(map(int, input().split())))

ans = [1 << 30] * (N + 1)  # 각 개수(인덱스)마다 최소거리를 저장하기 위해 아주큰값으로 초기화

for i in range(N):
    for j in range(N):
        mid_x, mid_y = arr[i][0], arr[j][1]  # 모든점의 좌표를 설정

        distance = []
        for h in range(N):  # 한점에서 부터 모든 점까지의 거리를 저장
            distance.append(abs(mid_x - arr[h][0]) + abs(mid_y - arr[h][1]))
        distance.sort()  # 최소 거리순으로 정렬
        sum_ = 0  # 각 거리마다 최소 거리를 저장
        for dist in range(N):
            sum_ += distance[dist]  # 각 좌표개수마다 거리를 더해준다.
            if ans[dist + 1] > sum_:  # 현재 거리에 저장된 최소거리보다 지금 구한 거리가 더 최소라면
                ans[dist + 1] = sum_  # 그값을 저장

print(*ans[1:])