[Python] 17430번 가로등

https://www.acmicpc.net/problem/17430

17430번: 가로등

---

 

22/11/22

 

 

예전에 해결하려다가 실패하여 오랫동안 북마크란에 있었던 문제로, 드디어 해결하였다.

 

개인적으로는 왜 기하학 문제인지 잘 모르겠고, 오히려 정렬 문제에 가까운 문제라고 생각한다.

---

 

문제 접근 방식:

 

 

문제 자체는 정말 간단하다.

2차원 공간 위에 가로등이 $N$개 배치되어 있다. $i$번째 가로등의 위치는 $(x_i, y_i)$이고, 각 좌표는 정수이다. 서로 다른 가로등의 위치가 같은 경우는 없다. 두 가로등 $i$와 $j$$(i < j)$가 있을 때, $(x_i, y_j)$와 $(x_j, y_i)$에 가로등이 있으면, 가로등 $i$와 $j$는 균형이 잡혀있다고 한다. 모든 가로등 쌍이 균형잡혀 있는지 아닌지 구해보자.

 

하지만, 이를 해결하는 데에는 아이디어가 필요했다.

 

일단 $N$의 범위가 최대 $200,000$까지 이기 때문에, 모든 가로등의 쌍이 균형잡혀있는지 일일히 확인하는 $O(n^2)$의 알고리즘으로는 시간초과가 날 수 밖에 없다.

 

때문에, $O(n)$의 시간 복잡도를 가지고 해결할 수 밖에 없다.

 

 

이를 위해서 먼저 정렬을 시행해주었다.

 

물론, 파이썬에서는 Tim sort알고리즘으로 $O(n\ \mathrm{log} \ n)$의 시간복잡도를 요하기는 하지만, 여기선 $\mathrm{log}\ n$의 최대 범위가 기껏 해야 $10$안쪽으로 들어오기 때문에 사실상 상수를 곱하는 것과 같다.

 

따라서, $O(n)$의 시간 복잡도와 매우 유사한 시간이 걸린다고 할 수 있다.

 

 

어쨌든 이렇게 정렬을 한 후, 두 가로등 쌍이 균형잡혀 있을 때의 성질을 이용하여 문제를 해결하였다.

 

만약, 두 가로등 쌍 $(x_i, y_i)$와 $(x_j, y_j)$가 있는데, $x_i = x_j$라면, 두 가로등 쌍은 균형잡혀있다고 말할 수 있다.

 

왜냐하면,  $(x_i, y_i) = (x_j, y_j)$이여서, $(x_i, y_j) = (x_j, y_i)$가 항상 성립하기 때문이다.

 

예를 들어, 내가 두 가로등 쌍을 $(3, 5)$와 $(3, -1)$을 뽑았다고 해보자.

 

그렇다면 $y$의 값을 서로 바꾼다고 해도 서로 원래 있었던 좌표가 나오기 때문에 두 가로등 쌍은 항상 균형 잡혀있다고 말할 수 있다.

 

따라서, 두 가로등 쌍을 뽑았을 때, $x$좌표가 같은 것을 뽑는 것은 사실 상 무의미하다고 볼 수 있다.

 

비슷한 이유로, 두 가로등 쌍을 뽑았을 때, $y$좌표가 서로 같은 것을 뽑는 것 또한 무의미 하다.

 

 

문제는 두 가로등 쌍을 뽑았을 때 서로 $x$좌표와 $y$좌표가 다른 경우이다.

 

이 경우는, 모든 가로등 쌍이 항상 균형잡혀 있으려면 아래와 같은 조건을 만족을 시켜야 된다.

 

만약 $(x_i, y_i)$와 $(x_j, y_j)$를 뽑는다면 두 개가 균형을 이루고 있어야 하므로, $(x_i, y_j)$와 $(x_j, y_i)$가 존재해야 한다.

 

마찬가지로, $(x_i, y_j)$와 $(x_j, y_i)$를 뽑는다면 두 개가 균형을 이루고 있어야 하므로, $(x_i, y_i)$와 $(x_j, y_j)$가 존재해야 한다.

 

다시 말해, $x_i$와 $x_j$를 고정한 채로 $y_i$와 $y_j$만 다르게 하여 두 쌍을 뽑는다면, 항상 두 가로등 쌍이 균형 잡혀있을 조건이 "$x_i$에 대한 모든 $y$좌표의 값들과 $x_j$에 대한 모든 $y$좌표의 값들이 모두 같아야만 한다."라는 것이다.

 

 

예를 들어보자.

 

예제 입력 1의 첫번째 케이스를 보면 다음과 같은 쌍들이 입력값으로 들어온다.

 

$$(2, 3), (2, -3), (2, 1), (-2, 3), (-2, -3), (-2, 1)$$

 

유심히 보면, $x$좌표를 다르게 뽑으면 남은 $y$좌표의 값들이 $3, -3, 1$로 항상 같다.

 

따라서, $x$좌표를 $2$와 $-2$로 고정해놓고 $y$좌표만 다르게 뽑아도 항상 이에 대응하는 쌍이 존재하기 때문에 균형잡혀있다고 말할 수 있다.

 

 

따라서, 먼저 입력받은 모든 가로등의 좌표들을 정렬한 뒤, for문으로 반복하여 돌다가 $x$좌표가 달라지는 지점을 찾았다.

 

그 지점까지가 $x$좌표가 같은 지점이 되는 것이므로, 이를 한 유닛이라고 생각했다.

 

이 한 유닛에 있는 모든 $y$좌표의 값들을 다음 유닛과 계속 비교해가며, 다르다면 균형이 잡혀있지 않은 것으로 판단했다.

 

만약 전부 다 비교했는데도 모든 유닛들이 맨 처음 유닛의 값과 전부 같다면 균형이 잡혀있는 것으로 판단했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

 

# 17430번 가로등
# 정렬
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    num_li = sorted(tuple(map(int, input().rstrip().split())) for _ in range(N))
    idx = N-1
    for i in range(N-1):
        if num_li[i][0] != num_li[i+1][0]:
            idx = i
            break
    one_unit = [num_li[i][1] for i in range(idx+1)]
    k = len(one_unit)
    for i in range(idx+1, N):
        if num_li[i][1] != one_unit[i%k]:
            print('NOT BALANCED')
            break
    else:
        print('BALANCED')