[백준] #1090 체커 (파이썬)

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

 

문제

N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

 

---

나(이곳저곳에서도움을받은)의 풀이

n = int(input())
position = [list(map(int, input().split())) for _ in range(n)]
answer = [int(1e9)] * n #int(1e9)는 정수 중에서 가장 큰 값!

for x in position:
    for y in position:
        costs = []
        for xx, yy in position:
            costs.append(abs(x[0]-xx)+abs(y[1]-yy))
        costs.sort()
        cost = 0
        for i in range(n):
            cost += costs[i]
            answer[i] = min(answer[i], cost)
print(*answer)

 

일단 문제 이해부터가 중요 !

n개의 체커들이 한 좌표에 모인다고 할 때, 모든 체커들의 이동거리를 합했을 때 최소가 되는 좌표를 찾고
그 좌표까지 체커들이 이동하는 총 거리를 출력해야 됨 !

 

(지금부터 강의내용)

완전탐색으로 이 문제를 풀 경우에 대입시켜봐야 하는 경우의 수가 정말 많아지는데 (1,000,000개 이상) 문제를 잘 살펴보니 어차피 최소가 되는 좌표는 체커들의 좌표 중 하나 !

예를 들어 체커가 3개라면 체커들이 있는 3개의 좌표 중 한 곳이 최소가 되는 좌표인 것임 or 체커들 좌표 내 중간 지점이거나 !

이런 논리로 코드를 짜보겠어요 ~

 

1. 우선 체커들의 좌표를 하나씩 돌려가면서 각각의 걸리는 거리를 계산해줌 -> costs 에다가 더해주기

2. costs를 정렬한 후

3. 1개 모일 때의 최솟값, 2개 모일 때의 최솟값, ... 을 누적합으로 cost로 계산하면서 cost와 answer[i]를 비교해서 최솟값을 answer에 할당 !

 

✅ 정리하면!

1. (x, y)를 목표 좌표 후보로 설정

2. 모든 체커가 (x, y)로 이동하는 거리 계산

3. 이동 거리 정렬 → 최소 비용을 찾음

4. 각 체커를 점진적으로 모으면서 최적의 answer[i] 갱신 입니당

 

---

플래티넘이래더니 정말 어려워,, 이해하는데 한참 걸림,, 아직도 좀 찜찜하긴해요,, 흑흑슨