[Python/파이썬] 백준 15970번 화살표 그리기

15970번: 화살표 그리기

 

코드

n = int(input())
color = [[] for _ in range(n+1)]
for _ in range(n):
    x, y = map(int, input().split())
    color[y].append(x)

ans = 0

for i in range(1, n+1):
    color[i].sort()
    for j in range(len(color[i])):
        if j == 0:
            ans += color[i][j+1]-color[i][j]
        elif j == len(color[i])-1:
            ans += color[i][j]-color[i][j-1]
        else:
            ans += min(color[i][j]-color[i][j-1], color[i][j+1]-color[i][j])

print(ans)

 

같은 색의 점들 중 가장 거리가 가까운 점을 찾아서 화살표를 그리는 것이므로 우선 같은 색의 점끼리 분류하는 것이 필요하다. 그렇기 때문에 처음에 점들의 위치와 색을 입력받을 때 점의 색을 인덱스로 삼아 color배열에 점의 위치를 저장해준다. 예를 들어, 위치가 1, 색이 3인 점이라면 color[3].append(1) 이렇게 말이다.

 

점들의 위치와 색을 모두 입력받아 저장한 후에는 각 색마다 다음 과정을 반복한다.

1. i번째 색을 가진 점들을 오름차순 정렬.
2. 정렬된 점들 각각에서 가장 가까운 점까지의 거리를 구하여 ans에 더하기.

이때 color[i]의 길이가 1일 수도 있다고 생각할 수도 있지만 문제를 잘 읽어보면 "모든 점에 대해서 샅은 색깔을 가진 다른 점이 항상 존재한다"라는 말이 있었으므로 무조건 같은 색을 갖는 점들의 개수는 2개 이상임을 알 수 있다.