하나로 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1251

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

당신은 인도네시아 내의 N개의 섬들을 연결하는 교통시스템 설계 프로젝트인 ‘하나로’를 진행하게 되었습니다. 하나로 프로젝트는 천해의 자연을 가진 인도네시아의 각 섬 간 교통이 원활하지 않아 관광 산업의 발전을 저해하는 요소를 줄이고 부가 가치를 창출하고자 진행하는 프로젝트입니다. 본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다. 해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다. 아래 그림 1과 같은 경우, A섬에서 D섬으로는 연결되었지만 A섬으로부터 B섬, C섬에는 도달 할 수 없기 때문에 연결되지 않은 것입니다. 아래 그림2,3 와 같은 방법을 통해 인도네시아 내의 모든 섬들을 연결해야 하는 프로젝트입니다. 그림 3에서 B와 A처럼 직접적으로 연결된 경우도 있지만, B와 C처럼 여러 섬에 걸쳐 간접적으로 연결된 경우도 있습니다. 다만 인도네시아에서는 해저터널 건설로 인해 파괴되는 자연을 위해 다음과 같은 환경 부담금 정책이 있습니다. - 환경 부담 세율(E)과 각 해저터널 길이(L)의 제곱의 곱(E * L2)만큼 지불 총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계하시오. 64비트 integer 및 double로 처리하지 않을 경우, overflow가 발생할 수 있습니다 (C/C++ 에서 64비트 integer는 long long 으로 선언). 위의 그림 2은 환경 부담금을 최소로 하며 모든 섬을 연결하고 있지만, 그림 3는 그렇지 않음을 알 수 있습니다.

 

입력

가장 첫 줄은 전체 테스트 케이스의 수이다. 각 테스트 케이스의 첫 줄에는 섬의 개수 N이 주어지고 (1≤N≤1,000), 두 번째 줄에는 각 섬들의 정수인 X좌표, 세 번째 줄에는 각 섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000). 마지막으로, 해저터널 건설의 환경 부담 세율 실수 E가 주어진다 (0≤E≤1).

출력

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다. 같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.

예시

입력	출력
10 2 0 0 0 100 1.0 4 0 0 400 400 0 100 0 100 1.0 6 0 0 400 400 1000 2000 0 100 0 100 600 2000 0.3 9 567 5 45674 24 797 29 0 0 0 345352 5464 145346 54764 5875 0 3453 4545 123 0.0005	#1 10000 #2 180000 #3 1125000 #4 27365366 . . .

---

2. 문제풀이

노드N개를 N-1개의 간선으로 모두 연결해야 하는 문제이다. 이럴때는 프림 혹은 크루스칼을 이용해야 한다고 생각한다. 이 문제의 경우 노드만 주어져있고, 간선은 주어져 있지않아서 모든 간선이 연결되는 경우의 수를 만들어야 한다. 따라서 간선이 엄청많아지게 되는데 이럴경우 프림 알고리즘이 더 빠르다. (그렇지만 나는 크루스칼로 풀었다. 더 쉬워서..., 나중에 기회가 된다면 프림풀이도 추가) 크루스칼 알고리즘은 싸이클이 생기지 않는 한도내에서 가장 비용이 적은 간선을 순서대로 선택하는 방식이다. 문제를 풀면서 고생했던 부분은 원하는 결과가 잘 나오지 않았던건데 문제에서 거리^2 * 세율(E)를 하는데 이게 모든 거리를 더하는게 아니고 각 터널마다 거리를 계산해서 더 해야한다. 추가내용 : 생각해봤는데 거리구할때 어차피 루트를 씌워야 하는데 비용계산할때 제곱을 해야하니까 바로 거리에 E를 곱하는게 비용이 덜 들거 같아서 수정했습니다.

---

3. 소스코드

# D4 1251 하나로
# 크루스칼 알고리즘
import heapq
 
# 가능한 간선의 종류를 만들어주는 함수
def make_edge():
    for i in range(N):
        for j in range(i+1, N):
            # 거리를 계산한다. √( (x1 - x2)^2 + (y1 - y2)^2 )
            d = ((islands_y[i]-islands_y[j])**2 + (islands_x[i]-islands_x[j])**2)*E
            # 거리를 기준으로 정렬할꺼기 때문에 거리를 제일앞에두고 어디에서 어디로 가는지 표시
            heapq.heappush(distance, (d, i, j))
 
# 부모를 찾는 함수
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]
 
# 부모를 병합해주는 함수
def unoion_parent(a, b):
    x = find_parent(a)
    y = find_parent(b)
    # 번호가 작은쪽으로 병합된다.
    if x > y: parents[x] = y
    else: parents[y] = x
 
# 부모가 같은지 확인하는 함수 -> 싸이클 확인
def find(a, b):
    x = find_parent(a)
    y = find_parent(b)
    return x != y
 
 
for t in range(int(input())):
    answer = 0
    count = 0
    N = int(input())
    islands_y = list(map(int, input().split()))
    islands_x = list(map(int, input().split()))
    distance = []
    # 부모의 정보를 저장하는 변수
    parents = [i for i in range(N)]
    E = float(input())
    # 모든 간선정보를 만들어주고
    make_edge()
    # 간선을 하나씩 꺼내며 체크, 간선의 최대개수는 N-1개이므로 끝나기전에 달성하면 종료
    while distance and count != N-1:
        # 정보를 꺼내서
        d, a, b = heapq.heappop(distance)
        # 부모가 다르다면
        if find(a, b):
            # 비용을 저장하고
            answer += d
            # 선택한 간선개수 증가하고
            count += 1
            # 부모를 병합
            unoion_parent(a, b)
    # 반올림 처리는 0.5를 더하고 정수로 변환하면 된다.
    answer = int(answer+0.5)
 
 
    print('#{} {}'.format(t+1, answer))