[백준/3780] 네트워크 연결 (Python)

Problem : https://www.acmicpc.net/problem/3780

3780번: 네트워크 연결

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:14:10

 

---

 

문제 설명

 

 

종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.

어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.

클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이다.
위 방식을 통해 클러스터 A와 B는 새로운 클러스터로 합쳐지며, 이 클러스터는 B의 센터에 의해 제공된다.
이러한 병합 과정을 거치던 중에, 각 기업에서 현재 센터까지 연결되는 라인의 길이가 총 얼마나 되는지에 관한 문의가 들어왔다. 서현이를 위해 병합하는 과정과 그 과정에서 통신센터와 각 기업을 잇는 라인의 길이를 구하는 프로그램을 작성해보자.

 

 

입력 및 출력

 

입력

 

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 개의 줄에 걸쳐 아래 두 가지 종류의 명령어가 들어온다.

 

• E I – 기업 I와 현재 I의 센터까지의 거리를 출력한다.
• I I J – 센터 I를 기업 J에 연결한다.

 

각 테스트케이스의 끝에는 단어 O가 주어진다. 각 테스트케이스에서 명령어의 총 개수는 200,000개를 넘지 않으며, 그중 I 명령어의 개수는 N개보다 작다.

 

출력

 

E 명령어가 들어올 때마다 한 줄에 해당 거리를 출력한다.

 

입력 예시

 

1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O

 

출력 예시

 

0
2
3
5

 

 

---

 

풀이

 

유니온 파인드로 간단하게(?) 풀 수 있다.

 

유니온 파인드의 핵심 중 하나는 find 과정에서 parent를 전부 갱신하여 이후 호출 시 상수 시간에 parent를 반환하는 기법으로 볼 수 있다. 우리는 이 parent 갱신 도중, 현재 노드와 parent간의 거리를 같이 갱신할 수 있다면 I 명령어를 효율적으로 처리할 수 있다는 개념을 떠올릴 수 있다. 

 

E I 명령어가 주어지면, I가 본인의 parent와 같아질 때까지 I를 갱신해나가면 된다. 이 때 초기 distance 갱신은 부모의 distance를 상속받아 더하는 식으로 초기화할 수 있다.

I I J 명령어는 더욱 간단한데, I의 parent를 J로 바로 지정해주면 된다. 이 때, 센터 I의 distance는 0이므로, i의 distance를 abs(i - j) % 1000으로 갱신해주자. 이후 find에서 모든 distance가 반영될 것이다.

 

풀이 코드

import sys
input = sys.stdin.readline

def find(a) :
  if a == parents[a] :
    return a

  pa = find(parents[a])
  dist[a] += dist[parents[a]]
  parents[a] = pa
  return pa

def solve() :
  global parents, dist
  N = int(input())
  parents = list(range(N+1))
  dist = [0]*(N+1)
  while True :
    q, *cmd = input().split()
    if q == 'E' :
      i = int(cmd[0])
      find(i)
      print(dist[i])
    elif q == 'I' :
      i, j = map(int, cmd)
      parents[i] = j
      dist[i] += abs(i - j) % 1000
    if q == 'O' :
      break
  del parents

for _ in range(int(input())) :
  solve()

풀이 완료!