글 읽기 - 코딩 질문

goodsosbva 3년 전 0

문제를 풀고, 비록 개념적인 부분을 참고해서 풀었기때문에 다른사람들에

코드도 공부해서 좀더 심도있는 이해가 필요한거같아 맞은분들 코드를 둘러보다가

이해가 안되는 부분이 있어서 질문합니다.

이 문제는 기본적으로 분할정복으로 문제를 풀자나요??

간단하게 요약하면

x축기준으로 d이내에 점을 찾고, 그다음 y축 기준으로 d이내에 점을 찾아서

그점에서 최소값을 찾는것.

근데 여기 코드에는 # 표시해둔 부분이 추가되어 있던데..

설명을 보면 모두 오른쪽에있을때 왼쪽에 있을때는 무시하는 거 같던데

왜그러는지 혹시 아시는 분 있을까요?

def dist(x1, x2):
    return (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2


def solve(coords, N):
    
    if(N == 2):
        return dist(coords[0], coords[1])
    
    elif(N == 3):
        return min(dist(coords[0], coords[1]), dist(coords[1], coords[2]), dist(coords[0], coords[2]))
    
    mid = (coords[N//2][0] + coords[N//2-1][0]) // 2
   
    d = min(solve(coords[:N//2], N//2), solve(coords[N//2:], N//2))
    
   
    short_check = []
    for subset in coords:
        if((mid - subset[0])**2 <= d):
            short_check.append(subset)
    short_check.sort(key = lambda x:x[1])
    
    if(len(short_check) == 1):
        return d
    else:
        y_check = d
        
        
        for i in range(len(short_check) - 1):
            for j in range(i+1, len(short_check)):\
                
                if(short_check[i][1] - short_check[j][1]) ** 2 > d:
                    break
                # 이부분이랑
                elif(short_check[i][0] < mid and short_check[j][0] < mid):
                    continue
                # 이부분을 코딩한 이유를 여쭈어봅니다...
                elif(short_check[i][0] > mid and short_check[j][0] > mid):
                    continue
                y_check = min(y_check, dist(short_check[i], short_check[j]))
                
    return y_check

import sys


N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]


coords_set = list(set(map(tuple,coords)))
if len(coords_set) != len(coords):
    print("0")
else:
    coords_set.sort() # sorted(coords, key=lambda x:-x[0])
    print(solve(coords_set, N))

jb0830 3년 전 1

15번째 줄에서 중심을 기준으로 (1) 왼쪽 영역에서 가장 가까운 두 점, (2) 오른쪽 영역에서 가장 가까운 두 점에 대해 이미 계산을 했기 때문에

모두 왼쪽에 있는 경우 -> (1) 에 해당

모두 오른쪽에 있는 경우 -> (2) 에 해당

이미 계산한 값에 대해 계산하지 않는 겁니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코딩 질문 - 파이썬

goodsosbva 3년 전 0

jb0830 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말