[그래프] 깊이/너비 우선 탐색(DFS/BFS)문제 6

문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, 
  costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 
  즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

---

오답노트

 

[처음에 접근한 방식과 코드]

• 처음에는 모든 섬이 연결만되면 된다는거니까 각 노드에 연결된 edge중 가중치가 가장 작은걸 선택하면 되는거 아닌가?라고 생각함
• 테스트 케이스는 통과됐지만, 채점에서 막힘

def solution(n, costs):
    answer = 0

    #각 노드에서 연결된 edge 중 가장 가중치가 적은거 고르면 되는거 아닌가?
    cost_graph = {}
    graph =[[] for _ in range(n)]
    low_cost = [0 for _ in range(n)]

    for x,y,z in costs :
        cost_graph[(min(x,y),max(x,y))] = z
        graph[x].append(y)
        graph[y].append(x)

    for i in range(n) :
        min_c = float('inf')
        for j in graph[i] :
            cost = cost_graph[(min(i,j),max(i,j))]
            if min_c > cost :
                print("cost : ", cost)
                min_c = cost
                low_cost[i] = (min(i,j),max(i,j))

    low_cost=set(low_cost)
    for i in low_cost :
        answer += cost_graph[i]

    return answer


n = 4
costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
print(solution(n,costs))

---

• 이전 코드의 문제점 → 전체 최소 연결이 보장되지 않음

• 예를 들어 이런 모양의 그래프가 있다고 할 때, 각 노드에서 가중치가 가장 작은 edge를 고르면 0,1,2 노드끼리 사이클이 생김
• 하지만 0-2 노드 사이에 간선이 없어도 전체 그래프 연결이 되기 때문에 이는 최소 연결이 아님
• 이런 모든 노드가 연결되고 사이클이 없는 그래프를 신장 트리(Spanning Tree)라고 하고
• 가중치가 있다고 했을 때, 모든 노드를 연결하며 사이클이 없는데 총 비용이 최소인 그래프를 최소 신장 트리(Minimum Spanning Tree) 라고 함
• MST 특징은 edge가 반드시 N-1개여야 하고
• MST를 만들기 위해 크루스칼 알고리즘과 Union-Find를 많이 씀

def solution(n, costs):
    answer = 0

    # 처음에는 모든 섬이 자기 자신 그룹
    parent = [i for i in range(n)]

    # x섬이 현재 어느 그룹에 속해있나? 확인
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # 두 그룹을 합치는 함수
    # a와 b를 연결해도 괜찮은가? 검사
    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False  # 이미 같은 그룹 → 사이클 발생

        parent[root_b] = root_a
        return True

    # 비용 기준으로 정렬해서 가장 비용이 싼 다리부터 보겠다
    # 근데 sort 함수는 기본적으로 각 리스트의 앞에서부터 비교하며 정렬함
    # key=lambda x: x[2] x는 costs 리스트의 각 원소를 의미 ex.costs[0]
    # 근데 우리는 비용 기준이니까 costs[i][2]를 봐야하니까 x[2]
    costs.sort(key=lambda x: x[2]) # 즉, costs 리스트의 2번 원소 기준으로 정렬해
    print(costs)

    edge_count = 0

    for a, b, cost in costs:
        if union(a, b):
            answer += cost
            print(parent)
            print(answer)
            edge_count += 1

            if edge_count == n - 1:
                break

    return answer


n = 4
costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
print(solution(n,costs))

---

시행착오 및 배운점

#1 MST(Minimum Spanning Tree) : 최소 신장 트리

MST : 가중치가 있다고 했을 때, 모든 노드를 연결하며 사이클이 없는데 총 비용이 최소인 그래프

[용어]

• 노드(Node) = 정점(섬) : 그래프에서 동그라미에 해당되는 부분
• 간선(Edge) = 거리(비용) : 그래프에서 선에 해당되는 부분
• 오른쪽 예시에서는 4개의 노드와 5개의 엣지로 구성됨

MST 특징

• MST를 만들기 위해 '크루스칼 알고리즘'과 'Union-Find'를 많이 씀
• 사용되는 Edge의 개수는 반드시 " Node 개수 - 1 "
• 사이클이 생기면 절대 X

1) Union-Find 알고리즘 (합집합 찾기)

• 대표적인 그래프 알고리즘
• '합집합 찾기' 또는 '서로소 집합(Disjoint-Set) 알고리즘'이라고 불림
• 여러개의 노드가 존재할 때, 2개의 노드를 선택해서 이 두 노드가 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘

2) 크루스칼 알고리즘(Kruskal Algorithm)

• 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
• 그래프를 입력받아서 MST(트리)를 만드는 알고리즘
• 모든 노드를 최대한 적은 비용으로 연결시키면 되기 때문에 아래 순서로 알고리즘 작동
  • 모든 Edge 정보(비용)를 기준으로 오름차순으로 정렬
  • 이후 비용이 적은 Edge부터 차근차근 그래프에 포함시키기
  • 단, 사이클이 발생되지 않아야 함 (사이클 발생 = 트리 X)
  • 따라서 사이클이 형성되는 경우 해당 Edge는 그래프에 포함시키지 않음

 

MST와 Union-Find, Kruskal 알고리즘

 

---

#2 lambda 함수

• 익명 함수라고도 불리며, 간단한 한줄짜리 함수를 정의할 때 사용됨
• 복잡한 로직이나 여러줄의 코드 처리에는 적합하지 않음
• 함수이지만 def 키워드를 사용하지 않고 lambda 키워드로 함수 정의
• 주로 filter(), map(), sorted() 등의 함수와 함께 사용되며 함수 인자로 전달되는 경우가 많음

lambda arguments : expression

 

• lambda : 람다 함수 정의 키워드
• arguments : 람다 함수에 전달되는 인자들. 쉼표로 구분해서 여러 인자 전달 가능
• expression : 표현식. 이 표현식의 결과가 람다 함수의 return 값이 됨

예를 들어 더하기 함수를 람다 함수로 구현하면 아래와 같음

add = lambda a, b: a + b
print(add(10,20))

30