[백준/파이썬] 1090번 체커

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

1090번: 체커

문제 해석

 

n개의 체커가 주어진다. 1 ~ n개를 골라 맨해튼 거리가 최소가 되는 좌표의 각 최소 거리의 합을 구하는 문제이다.

---

코드

 

input = __import__('sys').stdin.readline

# 1 ~ n 개를 골라 맨해튼 거리가 최소가 되는 좌표의 최소 거리를 구하여라

n = int(input())
arr = []
_xarr = []
_yarr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))
    _xarr.append(a)
    _yarr.append(b)

ans = [-1] * n

# 맨해튼 거리는 어차피 받은 배열안에 존재하기 때문에 배열만 확인하면 된다.
for sx in _xarr:
    for sy in _yarr:
        # 각 좌표에 대한 거리를 모아 놓는다.
        dist = []
        for ex, ey in arr:
            d = abs(ex - sx) + abs(ey - sy)
            dist.append(d)
        # 내림차순 정렬
        dist.sort()
        
        # 1 ~ N개 선택했을 때 최소 이동 횟수를 ans에 갱신해준다.
        temp = 0
        for i in range(len(dist)):
            d = dist[i]
            temp += d
            if ans[i] == -1: ans[i] = temp
            else: ans[i] = min(temp, ans[i])

print(*ans)

---

문제 풀이

 

맨해튼 거리에 위치한 좌표들의 최소 거리값은 항상 주어진 값에 위치할 수 있다. 따라서 주어진 좌표에 대해 완전 탐색을 통해 구해주면 된다.

 

먼저 각 x, y좌표의 모든 경우의 수와 주어진 좌표에 대한 거리를 dist 배열에 넣어주었다.

 

해당 dist 배열에서 차례대로 하나씩 더해가며 1 ~ n 개의 최소거리를 구해주고, 해당 값이 가장 작다면 ans 에서 값을 갱신해주었다.

 

모든 x, y좌표에 대한 최소 거리를 구해야하는데 주어진 x, y좌표에 대한 최소 거리만 구해 틀렸었다..