[SWEA 1251번] 하나로 (파이썬 풀이)

문제 바로 가기

🤔 문제 설명 및 입출력

---

- 문제의 저작권은 SWEA에 있습니다 -

 

 

✍ 접근 방법

---

이 문제는 시작 노드에서 도착 노드까지 도달하는 최소 비용을 구하는 문제가 아니라 ( 만약 문제가 이렇다면 다익스트라 계열 알고리즘으로 접근해야한다), 시작 노드에서 모든 노드를 순회하는데, 그 경로 중 최소 비용 경로를 구하는 문제이다.

 

모든 노드를 순회하는데, 최소 비용이 나오는 경로를 MST (Minimum Spanning Tree , 최소 신장 트리)라고 한다. 

 

MST를 구하는 대표적인 알고리즘으로는 프림 알고리즘과, 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘은 union-find 개념을 적용해야하는데, 내가 이것에 익숙치 않아 프림 알고리즘으로 구현하기로 결심했다.

 

 

프림 알고리즘은 MST를 찾기 위한 그리디 알고리즘의 일종으로 아래 흐름을 따라 구현 된다.

 

1) 임의의 정점을 선택한다.

2) 선택한 정점과 연결된 노드들 중, 간선 중 가중치가 최소인 간선을 선택한다.

3) 1)에서 선택했던 정점과 2)에서 선택한 간선으로 이어진 노드를 하나로 합쳐 트리를 만든다.

4) 2)~3)을 반복하여 더 이상 선택할 노드가 없을 때까지 반복한다.

 

 

*  쉽게 말해 ( 노드 선택 ➡ 최소 간선으로 이어진 노드 선택 ) 을 반복한다고 생각하면서, 알고리즘을 구현해보자.

 

 

👨‍💻 소스 코드

---

• 파이썬

def prim(n):
    D[n] = 0
    # G[n][n] = 0 <-- 없어도 된다. 이미 밖에서 자기 자신에게 도달하는 거리는 0 인것으로 초기화 되어있다. ex) G[0][0] = G[1][1] = G[2][2] ... = 0

    U = []
    for _ in range(N):
        mini = float("inf")
        for idx in range(N):
            if  idx in U: continue
            if D[idx] < mini:
                mini = D[idx]
                key = idx
        U.append(key)

        for j in range(N):
            if j in U: continue
            # 이전에 풀었던 문제의 여파인가. 나도 모르게 조건을 G[key][j] + D[key] < D[j]으로 걸었다.
            # 이 문제에서 D[i]는 i번 섬에 부과되는 부담금이다. 그런데, 부과금이 부여되는 기준은 섬과 섬사이의 거리만으로 결정 되는것이고,
            # 이전 섬에 부여되었던 부과금은 하등 상관이 없기에  G[key][j]와 D[j] 만 비교하면 되는것이다
            if G[key][j] and G[key][j] < D[j]: #+ D[key] < D[j]:
                D[j] = G[key][j] #+ D[key]





TC = int(input())

for tc in range(1,TC+1):
    N = int(input())
    X = list(map(int,input().split()))
    Y = list(map(int,input().split()))
    E = float(input())
    # 그래프 생성 / 2차원으로 만들기
    G = [[0] * N for _ in range(N)]
    # 큰 output에 대해서 자꾸 삑이 나길래 뭐지 싶었는데, D에 넣은 적당히 큰 값보다 더 쎈 친구들이 와버렸다
    # 그래서 python에서 선언할수 있는 양의 무한대를 적었다
    D = [float("inf")] * N
    for i in range(N):
        for j in range(N):
            G[i][j] = (X[i] - X[j])**2 + (Y[i] - Y[j])**2 # 환경 부담금 구하기
            G[j][i] = G[i][j]

    prim(0)

    ans = 0
    for elem in D:
        ans += elem
    print('#{} {}'.format(tc, round(ans*E)))

 

* sample 데이터를 사용했을 때 대략 13초 정도 소요됨

🔥 강평

---

주석에도 적어놓았지만, 이번 문제풀이에서 발생했던 에러는 크게 2가지였다.

 

1. 가중치를 저장하는 D 리스트의 값을 문제에서 입력되는 값보다 적게 설정해두어 (0xfffff 정도로 적었던 것 같다) 일부 case에 대해서 오답이 나왔다. 그래서 초기값으로 inf 값을 넣어주었다. 여담으로, 이전에 벨만-포드 알고리즘으로 negative-cycle을 찾는 문제를 풀었는데 그 문제를 풀 적에는 inf 값을 넣어줘서 에러가 났었다. 이렇게 반대되는 상황으로 에러가 발생하니까 좀 재미있다.

[BOJ 1865][백준 1865번] 웜홀 (파이썬 풀이)

  2. 최소 가중치 값을 계산할 때 나도 모르게 (현재 지점의 가중치 + 간선 가중치 ) < ( 이동할 지점의 가중치) 수식을 통해서 MST 선정에 애로사항이 있었다. 많은 최소 비용 문제들에서 현재 지점의 가중치까지 계산해서 들고가는데, 이번 문제는 특이하게도 섬 간 비용만 고려하고 있었다. 문제를 꼼꼼히 읽지 않은 탓도 있겠지만, 나도 모르게 좀비처럼 코딩한것은 아닌지 반성을 해본다.

 

 

맨날 백준 문제만 푸는거 같아 SWEA 문제를 한번 풀어봤다.

SWEA 문제들은 코드배틀 데이때 열리는 문제가 아니면 경험치를 얻을 수가 없어서 손이 잘 안가는데, 그래도 문제 데이터와 풀이가 거진 다 공개되어있기 때문에 잘 모르는 알고리즘 연습하기에는 딱 좋은것 같다.