[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로

🤔문제 해결

1. D4 | MST - prim

2. 간선의 가중치를 값으로 하는 인접 행렬을 만든다

3. 최소 값을 갱신해줄 가중치 리스트, MST에 포함되지 체크하는 리스트, 부모노드 선택리스트를 만든다.

(여기서는 모든 노드가 연결될 수 있기 때문에 부모노드는 필요하지 않을 수 있음)

4. 시작점을 선택(여기서는 0)하고 간선을 돌며 탐색한다

 (1) 아직 MST에 포함되어 있지 않고, 가중치가 최소인 정점 u를 찾는다.

 (2) u를 MST에 포함시키고, 그 가중치를 결과값에 더해준다.

 (3) 가중치를 최솟값으로 갱신하기 위해 u에 인접하고 아직 mst가 아닌 정점(w) 중에서 key[w] > u-w 이면 갱신한다

5. 모든 노드를 선택할 때까지 4번을 반복한다.

 

💨 최소신장트리 알고리즘, 크루스칼과 프림중에서 프림을 선택하여 문제를 해결함.

 

💻소스 코드

 for tc in range(1, 1+int(input())):
    n = int(input()) # 섬의 갯수
    x = list(map(int, input().split())) # 섬의 x 좌표
    y = list(map(int, input().split())) # 섬의 y 좌표
    E = float(input()) # 세율

    # 인접 행렬 생성
    adj = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            adj[i][j] = ((x[i]-x[j])**2 + (y[i]-y[j])**2)
            adj[j][i] = ((x[i]-x[j])**2 + (y[i]-y[j])**2)

    # for row in adj:
    #     print(row)

    # key 가중치, mst 방문 개념, p 연결 노드
    INF = float('inf')
    key = [INF]*n
    mst = [False]*n
    p = [-1]*n

    # 시작점 선택: 나는 0선택함
    key[0] = 0
    cnt = 0
    result = 0
    while cnt < n:
        # 아직 mst가 아니고 key가 최소인 정점 선택 : u
        minKey = INF
        u = -1
        for i in range(n):
            if not mst[i] and key[i] < minKey:
                minKey = key[i]
                u = i

        # u를 mst로 선택
        mst[u] = True
        result += minKey
        cnt +=1

        # key값을 갱신
        # u에 인접하고 아직 mst가 아닌 정점 w에서 key[w] > u-w 이면 갱신
        for w in range(n):
            if adj[u][w] > 0 and not mst[w] and key[w] > adj[u][w]:
                key[w] = adj[u][w]
                p[w] = u # 나한테 찾아오는 친구

    print('#{} {}'.format(tc, round(result*E)))

 

📕문제 확인

출처: SW Expert Academy

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE

SW Expert Academy

당신은 인도네시아 내의 N개의 섬들을 연결하는 교통시스템 설계 프로젝트인 ‘하나로’를 진행하게 되었습니다.

하나로 프로젝트는 천해의 자연을 가진 인도네시아의 각 섬 간 교통이 원활하지 않아 관광 산업의 발전을 저해하는 요소를 줄이고 부가 가치를 창출하고자 진행하는 프로젝트입니다.

본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다.

해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다.

아래 그림 1과 같은 경우, A섬에서 D섬으로는 연결되었지만 A섬으로부터 B섬, C섬에는 도달 할 수 없기 때문에 연결되지 않은 것입니다.

 

 
다음 두 가지의 경우는 모든 섬이 연결된 것입니다.
 

 

위와 같은 방법을 통해 인도네시아 내의 모든 섬들을 연결해야 하는 프로젝트입니다.

그림 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는 케이스의 번호이다.

같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.