🧚‍♂️알고리즘🧚‍♂️ - 그래프 - 최소신장트리

🧚‍♂️최소신장트리 (최소 스패닝 트리)🧚‍♂️

"모든 노드"를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리

 

- 사이클을 포함하지 않는다 ( == 이미 방문한 노드를 다시 방문하지 않는다)

- 최소 신장 트리를 구성하는 에지의 개수는 항상 "전체 노드의 개수" -1 

 

=> 사이클을 알기 위한 유니온 파인드 알고리즘(find 연산)을 구현해야 함

=> 에지 중심이므로 에지 리스트로 구현해야 함

---

1. 에지 리스트로 그래프 구현 / 유니온 파인드 리스트 초기화

2. 에지 리스트의 그래프 데이터를 가중치 기준 오름차순 정렬하기

3. 가중치가 낮은 에지부터 연결 시도하기

- 연결 에지가 N-1이 될 때까지 반복하기

---

🥇골드 4 (기본 정석 문제!)

1197번: 최소 스패닝 트리

import sys
from queue import PriorityQueue

N,M = map(int,sys.stdin.readline().split())
qp = PriorityQueue() # 에지 정보 저장 큐 (에지리스트)

parent = [0] * (N+1) # 사이클확인(중복노드확인)용 유니온파인드 부모리스트
for i in range(N+1) :
    parent[i] = i

for i in range(M): 
    s,e,w =  map(int,sys.stdin.readline().split())
    qp.put((w,s,e)) # 가중치 오름차순 정렬

def find(a):
    if a == parent[a] :
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
def union(a,b):
    A = find(a)
    B = find(b)
    parent[A] = B

useEdge = 0
result = 0

while useEdge < N-1 : # 크루스칼 알고리즘
    w,s,e = qp.get()
    if find(s) != find(e):  # 연결 시 사이클이 생기지 않으면 
        union(s,e)
        result += w
        useEdge += 1

print(result)

크루스칼 알고리즘을 이용해서 최소신장트리를 구하는 문제인데, 크루스칼 알고리즘은 그리디의 일종으로, 우선순위 큐를 이용해 가중치가 가장 작은 애들부터 결과 루트(최소신장)를 연결하기 시작한다. 이때 순서대로! 가 아닌 작은 애들부터! 그리고 유니온 파인드 연산을 해서 시작,끝 노드가 부모가 같은 == 사이클이 생기는 애들은 나중에 다 만들었을 때 같은 노드를 여러 번 방문하게 되는 모양을 하게 되므로 패스한다.

 

음 근데 그리디로 해도 된다는 걸 어떻게 바로 알지

작은 거 먼저 연결했을크 때 작은 거가 없어야 나올 수 있는 최단루트는 없는 건가(사이클로 제거되는 작은 애 말고)

---

🥇골드 1

17472번: 다리 만들기 2

 

1. 섬으로 표시된 모든 점에 BFS를 실행하여 섬을 구분.

2. 모든 섬에서 다른 섬 연결 여부 확인. ( 다리의 길이가 2 이상일 시 에지 리스트 추가)

3. 수집한 모든 에지를 오름차순 정렬하여 최소 신장 트리 알고리즘 수행.

import sys
from collections import deque

imput = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

dir = [(0, 1), (0, -1), (1, 0), (-1, 0)] # BFS 상하좌우 탐색 

def condition(ni, nj):
    return ni < 0 or ni >= n or nj < 0 or nj >= m
            
# 1. BFS로 섬 구분짓기
def marking(y, x, mark):
    q = deque()
    q.append((y, x))
    graph[y][x] = mark
    visited[y][x] = True
    while q:
        i, j = q.popleft()
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj) or not graph[ni][nj] or visited[ni][nj]:   
                continue
            graph[ni][nj] = mark
            visited[ni][nj] = True
            q.append((ni, nj))

mark = 1
for i in range(n):
    for j in range(m):
        if graph[i][j] and not visited[i][j]:
            marking(i, j, mark)
            mark += 1

# 2. 섬 잇는 간선 모두 구하기    
edge = set()

def getDist(y, x, now):
    q = deque()
    for idx in range(4):
        q.append((y, x, 0, dir[idx]))
    while q:
        i, j, cnt, nowDir = q.popleft()
        if graph[i][j] != 0 and graph[i][j] != now:
            if cnt > 2:
                edge.add((cnt - 1, now, graph[i][j]))
            continue
        ni, nj = i + nowDir[0], j + nowDir[1]
        if condition(ni, nj) or graph[ni][nj] == now:   continue
        q.append((ni, nj, cnt + 1, nowDir))

for i in range(n):
    for j in range(m):
        if graph[i][j] != 0:
            visited = [[False] * m for _ in range(n)]
            getDist(i, j, graph[i][j])

# 3. 최소 신장 트리 알고리즘 수행
edge = list(edge)
edge.sort()

def findParent(parent, x):
    if x != parent[x]:
        parent[x] = findParent(parent, parent[x])
    return parent[x]

def unionParent(parent, a, b):
    a = findParent(parent, a)
    b = findParent(parent, b)
    if a > b:
        parent[b] = parent[a]
    else:
        parent[a] = parent[b]
    
parent = [i for i in range(mark)]

result = 0

num = 0
for cost, a, b in edge:
    if findParent(parent, a) != findParent(parent, b):
        num += 1
        unionParent(parent, a, b)
        result += cost
        
if result == 0 or  num != mark - 2:
    print(-1)
else:   
    print(result)

윽..다음에 다시 한 번 더

[Python/파이썬] 백준 17472번: 다리 만들기 2

---

🥇골드 1

1414번: 불우이웃돕기

인접 행렬으로 입력이 제공  => 최소 신장 트리가 가능한 형태인 에지 리스트로 변형하는 것이 관건!

 

1. 문자열을 숫자로 변환하여 총합(가중치) 저장

2. 에지 리스트로 저장

3.최소 신장 트리 알고리즘 진행

4. 랜선의 총합 - 최신트 값 이 결과값 (단 N-1 에지 개수가 되지 않으면 -1 출력)(모든 컴퓨터 연결 불가 의미)

 

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())
qp = PriorityQueue() # 에지 정보 저장 큐 (에지리스트)

sum = 0 #모든 랜선 합
for i in range(N): 
    Nlist =  sys.stdin.readline().rsplit()[0]
    for j in range(N):
        if 'a' <= Nlist[j] <= 'z':
            w = ord(Nlist[j])-ord('a') + 1
        elif 'A' <= Nlist[j] <= 'Z':
            w = ord(Nlist[j])-ord('A') + 27
        else:
            w = 0 #가중치 0일 때
        sum += w #랜선전체길이
        if i != j and w != 0: # 같은 컴퓨터 아니고 연결 0 아니고
            qp.put((w,i,j)) # 가중치 오름차순 정렬


parent = [0] * (N+1) # 사이클확인(중복노드확인)용 유니온파인드 부모리스트
for i in range(N+1) :
    parent[i] = i

def find(a):
    if a == parent[a] :
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
def union(a,b):
    A = find(a)
    B = find(b)
    parent[A] = B

useEdge = 0
result = 0

# 크루스칼 알고리즘
while qp.qsize() > 0 : #연결 안 되는 결과 있을 수 있으므로 N-1 때까지 도는 거 아님
    w,s,e = qp.get()
    if find(s) != find(e):  # 연결 시 사이클이 생기지 않으면 
        union(s,e)
        result += w
        useEdge += 1
if useEdge == N-1:
    print(sum - result)
else:
    print(-1)

소문자

ord(현재문자)-ord('a') + 1
대문자
ord(현재문자)-ord('A') + 27

---

+

🧚‍♂️크루스칼 알고리즘🧚‍♂️ / 🧚‍♂️프림 알고리즘🧚‍♂️

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)

---

표지 고민..