[백준/파이썬][Bronze I] Claustrophobic Cows - 6003

[Bronze I] Claustrophobic Cows - 6003

문제 링크

성능 요약

메모리: 110736 KB, 시간: 116 ms

분류

브루트포스 알고리즘, 기하학, 피타고라스 정리

제출 일자

2025년 3월 6일 19:07:05

문제 설명

Farmer John has acquired a set of N (2 <= N <= 2,000) touchy cows who are conveniently numbered 1..N. They really hate being too close to other cows. A lot.

FJ has recorded the integer X_i,Y_i coordinates of every cow i (1 <= X_i <= 100,000; 1 <= Y_i <= 100,000).

Among all those cows, exactly two of them are closest together. FJ would like to spread them out a bit. Determine which two are closest together and print their cow id numbers (i) in numerical order.

By way of example, consider this field of cows (presented on a typewriter grid that has slightly different proportions than you might expect):

                    10 | . . . . . . . 3 . . . . .
                     9 | . 1 . . 2 . . . . . . . .
                     8 | . . . . . . . . . . . . .
                     7 | . . . . . . . . . . 4 . .
                     6 | . . . . . . 9 . . . . . .
                     5 | . 8 . . . . . . . . . . .
                     4 | . . . . . 7 . . . . . . .
                     3 | . . . . . . . . . 5 . . .
                     2 | . . . . . . . . . . . . .
                     1 | . . . . 6 . . . . . . . .
                     0 ---------------------------
                                           1 1 1 1
                       0 1 2 3 4 5 6 7 8 9 0 1 2 3

Quick visual inspection shows that cows 7 and 9 are closest together (the distance separating them is sqrt(1*1+2*2) = sqrt(5), so the output would be '7 9' on a single line (without quotes, of course).

입력

• Line 1: A single integer: N
• Lines 2..N+1: Line i contains the coordinates of cow i expressed as two space-separated integers: X_i and Y_i=

출력

• Line 1: The two numerical IDs of the closest pair of cows (sorted)

풀이

 

처음 풀이는 아래.

import sys
input = sys.stdin.readline

def distance(x1, y1, x2, y2) :
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** (1/2)

def sol_6003() :
    N = int(input())    # The number of cows
    cows = [[0, 0]]

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


    mn_dist = 200_001
    res = [0, 0]
    for i in range(1, N) :
        for j in range(i + 1, N + 1) :
            # 같은 길이는 존재하지 않는다고 했으니까.
            if distance(cows[i][0], cows[i][1], cows[j][0], cows[j][1]) < mn_dist :
                mn_dist = distance(cows[i][0], cows[i][1], cows[j][0], cows[j][1])
                res = [i, j]

    print(*res)
sol_6003()

이것은 다른 분꺼 참고한 후 조정한 답변이다.

def distance(x1, y1, x2, y2) :
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2)
def sol_6003() :
    N = int(input())    # The number of cows
    cows = [list(map(int, input().split())) for _ in range(N)]
    mn = 200_001 ** 2
    cow1 = cow2 = 0

    for i in range(N) :
        for j in range(i) :
            d = distance(cows[i][0], cows[i][1], cows[j][0], cows[j][1])
            if d < mn :
                mn = d
                cow1 = j + 1
                cow2 = i + 1

    print(cow1, cow2)

sol_6003()

기본적인 로직은 같다. 아래가 조금 더 깔끔해서 아래 답변도 추가해놓았다.

x, y 의 최대점에 대해서 생각한 후, mn을 고려하였다.

위 아래 상관없이 거리의 최소값을 구하고, 거리의 최소값을 구한 다음, 이때의 i, j 값을 갱신한다. 

이 로직만 구현하면 쉽게 해결할 수 있는 문제였다.