3770 대한민국 (백준, python3)

 

시간 제한	메모리 제한
1초	128MB

문제

대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다.

대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다)

고속도로가 서로 교차하는 곳에는 휴게소를 지으려고 한다. 한 점에서 교차하는 고속도로는 최대 2개이다. 고속도로가 주어졌을 때, 고속도로가 교차하는 곳의 개수를 구하는 프로그램을 작성하시오.

 

입력

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고속도로의 정보는 숫자 2개로 이루어져 있다. 첫 번째 숫자는 동해안에 있는 도시의 번호이고, 두 번째 숫자는 서해안에 있는 도시의 번호이다.

고속도로의 개수는 40만개보다 작거나 같으며, 문제의 정답이 2⁶³-1보다 작거나 같은 경우만 입력으로 주어진다.

 

출력

각 테스트 케이스에 대해서, 교차점의 수를 케이스 번호와 함께 출력한다.

 

---

풀이

a와 a'을 잇는 도로와 b와 b'을 잇는 도로가 교차되는 조건은 이렇다.

1. a > b 그리고 a' < b'
2. a < b 그리고 a' > b'

도시의 번호가 서로 엇갈리는 경우만 교차하며 도시의 번호가 겹치는 경우는 교차된 것으로 보지 않기 때문에(예제 입력 1에서 확인할 수 있다.) 조건을 이렇게 둘 수 있다. 그렇다면 어떤 도시 c 와 c'을 잇는 도로의 경우, c보다 작은 번호의 도시에서 출발하면 c'보다 큰 범위로 이어진 도로들을 확인하면 되고, 반대의 경우도 확인하면 된다.

 

이때, 모든 도로를 놓은 상태로 하나하나 확인하게 되면 하나의 교차점을 두 도로에서 확인하므로 결과는 정답의 두 배가 된다. 이 방법으로 탐색하게 되면 모든 K개의 도로에 대해 모든 K-1개의 다른 도로의 교차 여부를 확인하므로 시간복잡도는 O(K²)이다. K의 범위가 400,000이하이므로 최악의 경우 연산횟수 1,600억회, 시간제한 1초를 가볍게 초과해버린다.

 

도로를 하나씩 놓으면서 교차되는 도로들을 세어나가면 중복되는 것 없이 한 도로에서만 교차점을 확인할 수 있다. 하지만 이렇게 해도 연산횟수는 절반으로 줄어 최악의 경우 800억회의 도로 교차 확인이 필요하다. 당연히 시간초과.

 

여기서 도로를 오름차순으로 정렬하고 하나씩 깔아 확인한다고 하면 지금 확인하는 도로보다 이후 도시에서 출발하는 선분은 없다. 따라서 여기서는 비교 범위가 반토막이 나는데 연결된 도시보다 번호가 높은 도시로 이어진 이전 도시들만 확인하면 된다. 그리고 도시들로 연결된 도로들의 수를 구간합으로 관리하면 빠르게 이 값을 뽑아낼 수 있다. 따라서 세그먼트 트리로 해결하면 O(KlogK)의 시간복잡도로 문제를 해결할 수 있다.

세그먼트 트리(Segment Tree)

 

세그먼트 트리를 설계해보자.

목표 노드는 노란색이다. 그 오른쪽 구간이 도시 번호가 더 큰 도시들이다. 우선 충분한 크기의 트리를 만들고 노드에 도착하면 이번 도로를 깔아야 하기 때문에 노드 값을 1씩 증가시키며 탈출한다.

 

 

여기서 탈출하며 확인하는 노드가 왼쪽 노드인 경우, 오른쪽 노드의 값을 반환해주며 더해나가야 한다. 지금 확인하는 도시보다 번호가 더 큰 도시들로 연결된 모든 도로의 수를 뽑아야 하기 때문이다. 세그먼트 트리의 쿼리를 따로 구현할 수도 있겠지만 구간의 시작은 현재 탐색한 노드의 다음 노드이고, 구간의 끝은 언제나 마지막 도시이기 때문에 따로 쿼리를 만들 필요가 없다.

 

따라서 탈출하며 노드 인덱스의 짝수여부를 확인하고 짝수 노드인 경우, 옆 노드의 값을 더해서 반환시켜준다.

 

 

정답 코드

import sys, math
input = sys.stdin.readline

def seg(tree, node, s, e, t):
    # 목표 노드에 도착하면
    if s == e:
        tree[node] += 1   # 노드의 값 1 증가
        # 짝수노드면 옆 노드 반환, 아니면 0 반환
        if node % 2 == 0:
            return tree[node+1]
        else:
            return 0
    
    ret = 0  # 반환할 구간 합
    m = (s+e)//2
    if t <= m:
        ret = seg(tree, node * 2, s, m, t)
    else:
        ret = seg(tree, node * 2 + 1, m + 1, e, t)

    tree[node] += 1  # 탈출하면서 노드의 값 1씩 증가
    
    # 짝수노드면 옆 노드 값을 더해서 반환, 아니면 그대로 반환
    if node % 2 == 0:
        return ret+tree[node+1]
    else:
        return ret

def solution():
    N,M,K = map(int,input().split())
    road = [tuple(map(int,input().split())) for _ in range(K)]
    road.sort()     #  도로 정렬
    tree = [0]*(1<<math.ceil(math.log2(M))+1)
    crossed = 0
    
    # 모든 새로운 도로에 대해 구간 합 누적해서 더하기
    for e,w in road:
        crossed += seg(tree, 1, 1, M, w)
    return crossed

T = int(input())
for t in range(1,T+1):
    print("Test case {}: {}".format(t,solution()))