BOJ 2261 가장 가까운 두 점 python

2022년 12월 06일
#division and conquer#algorithm#boj#python

문제

가장 가까운 두 점

풀이

분할 정복, 스위핑 알고리즘으로 풀이가 가능한 문제인데, 스위핑은 파이썬으로 시간복잡도를 줄이기 어려워서 분할 정복을 이용하였다.

  1. 점을 x좌표 기준으로 모두 정렬하고, 중간 값을 기준으로 두 영역으로 나눈다.
  2. 하나의 영역 안에서 점 2개를 뽑는 경우와, 두 영역에서 하나씩 점을 뽑는 경우로 나눠 계산해주면 된다.

최소값을 갱신하면서 가지치기를 하는 부분이 핵심인 문제였다. 영역을 좀만 크게 잡아도 TLE를 받는다.

풀이 코드

import sys
rl = sys.stdin.readline
n = int(rl())
roc = [list(map(int, rl().split())) for _ in range(n)]
roc.sort()
 
def cal(a, a0):
    return (a[0]-a0[0])**2+(a[1]-a0[1])**2
 
def divCon(dots, dotNum):
    if dotNum == 2: return cal(dots[0], dots[1])
    elif dotNum == 3: return min(cal(dots[0], dots[1]),cal(dots[1], dots[2]),cal(dots[0], dots[2]))
 
    midx = (dots[dotNum//2][0]+dots[dotNum//2-1][0])//2
    mind = min(divCon(dots[:dotNum//2], dotNum//2), divCon(dots[dotNum//2:], (dotNum+1)//2))
 
    checkdot = []
    for x, y in dots:
        if (midx-x)**2>=mind:
            if x>midx: break
            continue
        checkdot.append([x,y])
    checkdot.sort(key = lambda x: x[1])
 
    for i in range(len(checkdot)-1):
        for j in range(i+1, len(checkdot)):
            if (checkdot[i][1]-checkdot[j][1])**2>=mind: break
            mind = min(mind, cal(checkdot[i], checkdot[j]))
    return mind
 
print(divCon(roc, n))

관련 글

백준 2927 남극탐험 Python
https://www.acmicpc.net/problem/2927 트리에서 노드 연결, 단일 업데이트, 구간합 쿼리를 수행하는 문제이다. 연결 여부는 union-find로 관리하고, 먼저 모든 연결 쿼리를 수행하여 HLD를 해준다. 이후, 순서대로 쿼리를 처리하면 된다. HLD 과...
BOJ 25910 게이트웨이 정하기 python
문제 게이트웨이 정하기 풀이 비트 연산의 특징을 알아야 풀 수 있는 문제였다. 1. 임의의 노드에서 시작한 결과를 dp에 저장한다. 2. 각 비트를 0인 그룹과, 1인 그룹으로 나눈다.(temp에 1일 경우만 저장) 3. 모든 노드에 대해 헤더와 XOR연산으로 비용을 구한다. 4....
programmers 행렬과 연산 python
문제 행렬과 연산 풀이 표를 적당히 쪼개서 deque로 풀면 된다. 맨 왼쪽 열과 맨 오른쪽 열을 따로 저장해서 deque 2개를 만들고, 각 행의 인덱스를 저장한 deque를 만든다. 연산 시, q, leftq, rightq에 저장된 마지막 인덱스를 맨 앞으로 옮겨준다. 연산 시...