[코독하구만 팀] 2020.12.30(수) - 2주차 개인 결과

prim와 kruskal를 개념과 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써

둘의 차이와 알고리즘 동작방식에 대해 확실하게 아는 계기가 되었다.

 

- 목표 -

codekodo.tistory.com/8

[코독하구만 팀] 2020.12.30(수) - 2주차 개인 목표

 

1. prim 알고리즘

import heapq

def prim(edges, vertices, n):
    queue = []
    heapq.heappush(queue, [0, vertices[0], vertices[1]])    # 가중치, 시작, 도착

    visit = {}
    for i in vertices:
        visit[i] = False

    result = []
    sum = 0

    while queue:
        h = heapq.heappop(queue)
        if visit[h[2]] == True:     # 도착지점 방문여부 확인
            continue
        else:
            visit[h[2]] = True
            sum += h[0]     # 가중치 합산
            result.append([h[1], h[2], h[0]])
        
        for e in edges[h[2]]:   # 다음 도착지점
            if (visit[e[0]]) : continue # 다음 도착지점 방문여부 확인
            heapq.heappush(queue, [e[1], h[2], e[0]])   # 가중치, 시작, 도착
            
    for e in visit.values():    # 방문하지 않은 노드가 있을 경우(고립된 노드 존재)
        if e == False:
            sum = 0
            break

    return sum

def main():
    n, m = map(int, input().split())
    vertices = input().split()
    edges = {}

    for i in vertices:
        edges[i] = []

    for _ in range(m):
        u, v, c = input().split()   #시작, 도착, 가중치
        c = int(c)
        edges[u].append([v, c])     #양방향 그래프
        edges[v].append([u, c])

    print(prim(edges, vertices, n))

if __name__ == "__main__":
    main()

 

 

2. kruskal 알고리즘

parent = {}
rank = {}

def make_set(v):
    parent[v] = v
    rank[v] = 0

def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
    return parent[v]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]:
                rank[root2] += 1

def kruskal(vertices, edges, n):
    for u in vertices:
        make_set(u)

    edges.sort()
    sum = 0

    for e in edges:
        cost, u, v = e      # 가중치, 시작, 도착
        if find(u) != find(v):  # 시작 정점과 도착 정점의 부모가 다를 경우
            union(u,v)
            sum += cost

    return sum

def main():
    n, m = map(int, input().split())
    vertices = []
    edges = []
    vertices = input().split()

    for _ in range(m):
        u, v, c = input().split()
        c = int(c)
        edges.append((c, u, v))     # 가중치, 시작, 도착

    print(kruskal(vertices, edges, n))

if __name__ == "__main__":
    main()

 

 

3. 가장 중요한 길

parent = {}
rank = {}

def make_set(v):
    parent[v] = v
    rank[v] = 0

def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
    return parent[v]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]:
                rank[root2] += 1

def kruskal(vertices, edges, n):
    for u in vertices:
        make_set(u)

    edges.sort()
    sum = 0

    for e in edges:
        cost, u, v = e      # 가중치, 시작, 도착
        if find(u) != find(v):  # 시작 정점과 도착 정점의 부모가 다를 경우
            union(u,v)
            sum += cost

    return sum

def main():
    n, m = map(int, input().split())
    vertices = []
    edges = []
    vertices = input().split()

    for _ in range(m):
        u, v, c = input().split()
        c = int(c)
        edges.append((c, u, v))     # 가중치, 시작, 도착
    
    standard = kruskal(vertices, edges, n)  # 기준이 되는 MST

    new_edges = []
    result = []     # 중요한 길을 저장할 리스트
    for i in edges:
        new_edges = edges.copy()
        new_edges.remove(i)
        if kruskal(vertices, new_edges, n) > standard:  # MST 값이 커지면 제거한 엣지가 중요한 길
            result.append([i[1], i[2]])
    
    print(len(result))

if __name__ == "__main__":
    main()

 

 

4. 1197번 최소 스패닝 트리

import heapq

def prim(edges, vertices, n):
    queue = []
    heapq.heappush(queue, [0, vertices[0], vertices[1]])    # 가중치, 시작, 도착

    visit = {}
    for i in vertices:
        visit[i] = False

    result = []
    sum = 0

    while queue:
        h = heapq.heappop(queue)
        if visit[h[2]] == True:     # 도착지점 방문여부 확인
            continue
        else:
            visit[h[2]] = True
            sum += h[0]     # 가중치 합산
            result.append([h[1], h[2], h[0]])
        
        for e in edges[h[2]]:   # 다음 도착지점
            if (visit[e[0]]) : continue # 다음 도착지점 방문여부 확인
            heapq.heappush(queue, [e[1], h[2], e[0]])   # 가중치, 시작, 도착
            
    for e in visit.values():    # 방문하지 않은 노드가 있을 경우(고립된 노드 존재)
        if e == False:
            sum = 0
            break

    return sum

def main():
    n, m = map(int, input().split())
    vertices = []
    for i in range(n):
        vertices.append(i+1)
    edges = {}
    for i in vertices:
        edges[i] = []

    for _ in range(m):
        u, v, c = map(int, input().split())   #시작, 도착, 가중치
        edges[u].append([v, c])     #양방향 그래프
        edges[v].append([u, c])

    print(prim(edges, vertices, n))

if __name__ == "__main__":
    main()

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

k906506/2020_Winter_Assemble-And-selfcode