[BOJ17430] 가로등 - Python

문제

풀이

임의의 가로등 A를 기준으로 모든 가로등 N이 (Ax, Ny) & (Nx, Ay)를 만족하면 Balance가 잡혀있다.

시간복잡도는 case당 dict에 저장(200,000) + A를 기준으로 완전탐색(200,000) = 400,000 정도이다.
case느 최대 5개로 2,000,000 정도이니 제한시간 0.5초를 가볍게 통과 할 수 있다.

import sys, math
ip = lambda:map(int, sys.stdin.readline().split())
T, *_ = ip()
for _ in range(T):
    N, *_ = ip()
    arr = [tuple(ip()) for _ in range(N)]
    m = {}
    # 가로등을 dict에 저장
    for i in range(N):
        x, y = arr[i]
        if not x in m:
            m[x] = {}
        m[x][y] = i

    # 가장 첫 가로등
    ox, oy = arr[0]
    is_nb = False
    # 나머지 가로등 만큼 반복
    for i in range(1, N):
        x, y = arr[i]
        # (ox, y)가 아니면
        if not y in m[ox]:
            is_nb = True
            break
        # (x, oy)가 아니면
        if not oy in m[x]:    
            is_nb = True
            break
    if is_nb:
        print("NOT BALANCED")
    else:
        print("BALANCED")