[알고리즘] BOJ 1647 도시 분할 계획 #Python

김상현·2022년 10월 24일
0

알고리즘

목록 보기
215/301
post-thumbnail

[BOJ] 1647 도시 분할 계획 바로가기

📍 문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.


📍 입력

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.


📍 출력

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.


📍 풀이

💡 고찰

  • 크루스칼 최소 신장 트리(Kruskal Minimum Spanning Tree) 알고리즘을 활용하여 문제를 해결하였다.
  • 처음에는 최소 간선을 기준으로 집합(set) 자료구조를 이용하여 문제를 해결하기 위해 countryA, countryB 집합을 생성하여 해당 문제에 집의 번호를 추가하는 형식으로 접근하였다.
  • 집합 자료구조로 문제를 해결하는데 발생한 문제countryA, countryB 집합에 처음 집의 원소를 추가하는 알고리즘을 작성하는 것이었다.
  • 기준을 정하기 위해서 여러 시도를 해보았지만, 주어진 자료값에 따라서 countryA 에 들어갈 집의 원소가 countryB에 들어가는 문제가 발생하였다.
  • 결국 집합으로 문제를 해결하는 것은 올바른 방법이 아니라는 것을 인정하고, 구글링을 통해 Kruskal 알고리즘을 사용해야 한다는 것을 알게 되었다.
  • Kruskal 알고리즘은 사이클이 생기지 않는 최소한의 연결값을 찾는 알고리즘이다.
  • Kruskal 알고리즘에서 마지막 간선을 추가하지 않는다면 2개의 마을로 분할된다는 것을 생각해서 N-2 개의 간선으로 구성된 값을 결과값으로 출력하는 방식을 이용하였다.

📌 문제 풀이

✏️ 1. 입력받은 길의 정보(edges)를 길의 유지비(x[2]) 기준으로 정렬

edges.sort(key=lambda x : x[2])

✏️ 2. Kruskal 알고리즘을 활용하기 위한 UNION & FIND 함수 작성

def union(x, y):
    x = find(x)
    y = find(y)
    graph[max(x,y)] = min(x,y)

# FIND
def find(x):
    if x != graph[x]:
        graph[x] = find(graph[x])
    return graph[x]

✏️ 3. 주어진 길의 정보(edges)를 이용항 Kruskal 알고리즘 적용

for A, B, C in edges:
        if N == 2: break
        if find(A) != find(B):
            answer += C
            union(A,B)
            N -= 1
  • 만약 현재 연결한 길의 수가 N - 2개(2개의 마을로 분할된 상태)라면 Kruskal 알고리즘을 종료한다.
  • 만약 현재 주어진 길을 연결할 경우 마을에 사이클이 생기는 경우 if find(A) != find(B):
    즉, 굳이 연결되어도 되지 않아도 되는 길은 연결하지 않는다.
  • 위의 경우를 제외한 길은 find() 함수를 통해 연결하고 현재 길의 유지비를 answer 에 추가한다.

✍ 코드

from sys import stdin

def solution(N,edges):
    answer = 0
    graph = list(range(N+1))

    # UNION
    def union(x, y):
        x = find(x)
        y = find(y)
        graph[max(x,y)] = min(x,y)

    # FIND
    def find(x):
        if x != graph[x]:
            graph[x] = find(graph[x])
        return graph[x]

    # KRUSKAL MINIMUM SPANNING TREE
    for A, B, C in edges:
        if N == 2: break # 마을이 두개로 분리된 상태
        if find(A) != find(B): # 사이클 형성하는 간선 무시
            answer += C
            union(A,B)
            N -= 1

    return answer

# input
N, M = map(int,stdin.readline().split())
edges = []
for _ in range(M):
    A, B, C = map(int,stdin.readline().split())
    edges.append((A,B,C))
edges.sort(key=lambda x : x[2]) # 가중치(C)를 기준으로 정렬

#result
result = solution(N,edges)
print(result)
profile
목적 있는 글쓰기

0개의 댓글