[Python] 그래프(2)

# 8-5. 벨만-포드

벨만-포드(bellman-ford-moore) 알고리즘이란?

• 그래프에서 최단 거리를 구하는 알고리즘
• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로까지의 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행할 수 있으며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
• 시간 복잡도 : O(VE)

벨만-포드 핵심 이론

• 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기
  • 에지 리스트는 출발 노드, 종료 노드, 가중치 변수로 구성돼 있다.
• 모든 에지를 확인해 정답 리스트 업데이트 하기
  • 업데이트 반복 횟수는 노드 개수 -1이다.
  • 모든 에지 E = (s,e,w)에서 D[s]!=max값 이며 D[e]>D[s]+w일 때 D[e]=D[s]+w로 리스트 값을 업데이트 한다.
  • 음수 사이클이 없을 때 N-1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 감의 최단 거리를 알려주는 정답 리스트가 완성된다.
• 음수 사이클 유무 확인하기
  • 모든 에지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인한다. 음수 사이클이 존재하면 이 사이클을 무한히 돌수록 가중치가 감소하므로 최단 거리를 구할 수 없다.

 

https://www.acmicpc.net/problem/11657

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edges = []
distance = [sys.maxsize]*(N+1)

for i in range(M): # 에지 데이터 저장
    start, end, time = (map(int, input().split()))
    edges.append((start, end, time))

# 벨만-포드 수행
distance[1] = 0

for _ in range(N-1):
    for start, end, time in edges:
        if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
            distance[end] = distance[start]+time

# 음수 사이클 확인
mCycle = False

for start, end, time in edges:
    if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
        mCycle = True

if not mCycle: # 음수 사이클 미존재
    for i in range(2, N+1):
        if distance[i]!=sys.maxsize:
            print(distance[i])
        else:
            print(-1)
else:
    print(-1)

• 에지 리스트에 에지 데이터를 저장한 후 거리 리스트를 초기화 한다.
• 벨만-포드 알고리즘을 수행한다.
  • 모든 에지 정보를 가져온 후 출발 노드!=INF 이고 출발 노드 거리 리스트 값+에지 가중치 < 종료 노드 거리 리스트값일 때 종료 노드의 거리 리스트 값을 업데이트 한다.
  • 노드 개수 -1번 만큼 위를 반복한다.
  • 음수 사이클 유무를 알기 위해 첫 과정을 반복한다.
• 음수 사이클이 존재하거나 거리 리스트 값이 INF인 경우 -1을 출력한다.

 

https://www.acmicpc.net/problem/1219

• 최단 거리를 구하는 벨만-포드 알고리즘을 반대로 최대 액수의 돈을 저장하도록 로직을 변경한다.
• 돈을 무한히 버는 케이스가 있다는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경한다.
• 예외 처리를 이용해 양수 사이클이 존재하지만 출발 노드에서 도착 도시에 가지 못하는 경우를 해결한다.
  • 에지의 업데이트를 N-1번이 아닌 충분히 큰 수(도시 개수 N의 최대치==100)만큼 추가로 돌리면서 업데이트를 수행한다.

 

import sys
input = sys.stdin.readline

N, sCity, eCity, M = map(int, input().split()) # 노드 수, 시작, 종료, 에지 수
edges = []
distance = [-sys.maxsize]*N # 최단 거리 리스트 초기화

for _ in range(M):
    start, end, price = map(int, input().split())
    edges.append((start, end, price))

cityMoney = list(map(int, input().split()))

# 변형된 벨만-포드 수행
distance[sCity] = cityMoney[sCity] # 출발 초기화

# 양수 사이클이 전파되도록 출분히 큰 수로 반복
for i in range(N+101):
    for start, end, price in edges:
        if distance[start] == -sys.maxsize: # 출발 노드가 미 방문 노드면 skip
            continue
        elif distance[start] == sys.maxsize:
            distance[end] = sys.maxsize
        # 더 많은 돈을 벌 수 있는 새로운 경로가 있는 경우 값 업데이트
        elif distance[end] < distance[start] + cityMoney[end] - price:
            distance[end] = distance[start] + cityMoney[end] - price
            if i>= N-1:
                distance[end] = sys.maxsize

if distance[eCity] == -sys.maxsize: # 도착 불가능
    print("gg")
elif distance[eCity] == sys.maxsize: # 양수 사이클 -> 무한대로 돈을 벌 수 있는 경우
    print("Gee")
else:
    print(distance[eCity])

• 도착 도시의 값에 따라 결과를 출력한다.
  • 도착 도시의 값이 MIN이고, 도착하지 못할 때 'gg'를 출력
  • 도착 도시의 값이 MAX고, 무한히 많이 벌 수 있을 때 'Gee'를 출력
  • 이외에는 도착 도시의 값을 출력한다.

1번 distance 업데이트 예시

 

---

# 플로이드-워셜

플로이드-워셜(floyd-warshall)이란?

• 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘이다.
• 음수 가중치 에지가 있어도 수행할 수 있고, 동적 계획법의 원리를 이용하여 알고리즘에 접근한다.
• 시간 복잡도 : O(V^3)

플로이드-워셜 핵심 이론

• A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 원리이다.
• 점화식 : D[s][e] = min(D[s][e], D[s][k]+D[k][e])
• 리스트를 선언하고 초기화 한다. D[s][e]는 노드 s에서 e까지의 최단 거리를 저장하는 리스트이다. s와 e의 값이 같은 칸은 0, 다른 칸은 INF로 초기화 한다.
• 최단 거리 리스트에 그래프 데이터를 저장한다. D[s][e]=W로 에지의 정보를 리스트에 입력한다.(인접 행렬 그래프 표현)
• 점화식으로 리스트를 업데이트 한다.
• 플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인하므로 시간 복잡도가 빠르지 않다. 따라서 일반적으로 노드 개수의 범위가 작다.

 

https://www.acmicpc.net/problem/11404

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
distance = [[sys.maxsize for j in range(N+1)] for i in range(N+1)]

for i in range(1, N+1): # 인접 행렬 초기화
    distance[i][i]=0

for i in range(M):
    s,e,v = map(int, input().split())
    if distance[s][e]>v:
        distance[s][e] = v

# 플로이드-워셜 수행
for k in range(1, N+1): # k가 가장 바깥쪽
    for i in range(1, N+1):
        for j in range(1, N+1):
            if distance[i][j] > distance[i][k] + distance[k][j]:
                distance[i][j] = distance[i][k] + distance[k][j]

for i in range(1, N+1):
    for j in range(1, N+1):
        if distance[i][j] == sys.maxsize:
            print(0, end=' ')
        else:
            print(distance[i][j], end = ' ')
    print()

• 그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구하는 알고리즘이다.
• 버스 비용 정보를 인접 행렬에 저장한다. 연결 도시가 같으면(i==j) 큰 수로 초기화 하고, 주어진 버스 비용 데이터 값(v)을 인접 행렬에 저장한다.
• 플로이드-워셜 알고리즘을 수행한다.
  • 두 도시 연결 비용 중 최솟값을 저장한다. distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
• 알고리즘으로 변경된 인접 행렬을 출력한다. 두 도시가 도달하지 못할 때에는 0을 출력한다.

 

https://www.acmicpc.net/problem/11403

N = int(input())
distance = [[0 for j in range(N)] for i in range(N)]

# 인접 행렬 데이터 저장
for i in range(N):
    distance[i] = list(map(int, input().split()))

# 변형된 플로이드-워셜 수행
for k in range(N):
    for i in range(N):
        for j in range(N):
            if distance[i][k]==1 and distance[k][j]==1:
                distance[i][j] = 1

for j in range(N):
    for j in range(N):
        print(distance[i][j], end = ' ')
    print()

• 입력 데이터를 인접 행렬에 저장한다.
• 플로이드-워셜 알고리즘을 수행한다. 단, 최단 거리를 구할 필요가 없으므로 중간 경로(K)가 존재하면 S와 E를 연결 녿드(1)로 저장한다
• 출력!. 

 

https://www.acmicpc.net/problem/1389

import sys
N, M = map(int, input().split())
distance = [[sys.maxsize for j in range(N+1)] for i in range(N+1)]

for i in range(1, N+1): # 인접 행렬 초기화
    distance[i][i] = 0

for i in range(M):
    s, e = map(int, input().split())
    distance[s][e] = 1
    distance[e][s] = 1

# 플로이드-워셜 수행
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if distance[i][j] > distance[i][k]+distance[k][j]:
                distance[i][j] = distance[i][k]+distance[k][j]

Min = sys.maxsize
Answer = -1

for i in range(1, N+1):
    temp = 0
    for j in range(1, N+1):
        temp += distance[i][j]
    if Min>temp: # 가장 작은 케빈 베이컨의 수를 지닌 i 찾기
        Min = temp
        Answer = i

print(Answer)

• 친구들이 직접 친구 관계를 맺은 비용을 1로 계산한다. i번째 row의 합이 i번째 사람의 케빈 베이컨의 수가 된다.
• 인접 행렬 생성 후 자기 자신이면(i==j) 0, 아니면 INF로 초기화 한다. 그리고 i와 j가 친구라면 distance[i][j]와 distance[j][i]를 1로 업데이트 한다.
• 플로이드-워셜 알고리즘을 수행한다.
• 케빈 베이컨의 수(각 행의 합)를 비교해 가장 작은 수가 나온 행 번호를 정답으로 출력한다. 같은 수가 있을 때는 더 작은 행 번호를 출력한다.

 

• BFS로도 풀 수 있다. 훨씬 효율적!

import sys
from collections import deque


def bfs(graph, start):
    num = [0] * (n+1)
    visited = [start]
    queue = deque()
    queue.append(start)

    while queue:
        a = queue.popleft()
        for i in graph[a]:
            if i not in visited:
                num[i] = num[a] + 1
                visited.append(i)
                queue.append(i)
    return sum(num)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

result = []
for i in range(1, n+1):
    result.append(bfs(graph, i))

print(result.index(min(result))+1)

 

 

---

# 8-7. 최소 신장 트리

최소 신장 트리(minimum spanning tree)란?

• 모든 노드를 연결할 때 사용된 에지들의 가중치를 최소로 하는 트리이다.
• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.  

최소 신장 트리 핵심 이론

• 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화 하기
  • 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 에지 리스트의 형태로 데이터를 저장한다. 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.
  • 사이클 처리를 위한 유니온 파인드 리스트를 리스트의 인덱스 자리 값으로 초기화 한다.
• 그래프 데이터를 가중치 기준으로 정렬하기
• 가중치가 낮은 에지부터 연결 시도하기
  • 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결한다.
• 전체 노드가 N개 일 때, 연결한 에지의 개수가 N-1개가 될 때까지 위 과정을 반복한다.
• 총 에지 비용 출력

 

https://www.acmicpc.net/problem/1197

import sys
from queue import PriorityQueue
input = sys.stdin.readline

N, M = map(int, input().split())
pq =  PriorityQueue()
parent = [0]*(N+1)

for i in range(N+1):
    parent[i]=i

for i in range(M):
    s,e,w = map(int, input().split())
    pq.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)
    if a!=b:
        parent[b]=a

useEdge = 0
result = 0

while useEdge<N-1: # MST는 항상 N-1의 에지를 사용
    w,s,e=pq.get()
    if find(s)!=find(e): # 같은 부모가 아닌 경우만 연결
        union(s,e)
        result+=w
        useEdge+=1

print(result)

• 에지 리스트에 에지 정보를 저장 후 부모 노드 데이터를 초기화한다. 사이클 생성 유무 판단을 위해 유니온 파인드용 부모 노드(parent)도 초기화 한다.
• 크루스칼 알고리즘을 수행한다. 현재 미사용 에지 중 가중치가 가장 작은 에지를 선택하고, 이 에지를 연결 했을 때 사이클의 발생 유무를 판단한다.
• 에지를 더한 횟수가 N-1이 될때까지 반복하고, 반복이 끝나면 에지의 가중치의 합(answer)을 출력한다.

 

• 프림 일고리즘으로도 가능하다.
  • 임의의 정점을 선택
  • 해당 정점에서 갈 수 있는 간선을 minheap에 넣기
  • 최소값을 뽑아 방문하지 않았다면 연결

 

https://www.acmicpc.net/problem/17472

• 먼저 주어진 지도에서 섬으로 표현된 값을 각각 다르게 표현한다.
• 그 이후 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인해 에지 리스트를 만든다.
• 이후 MST를 적용한다.

import copy
import sys
from collections import deque
from queue import PriorityQueue
input = sys.stdin.readline

dr = [0,1,0,-1]
dc = [1,0,-1,0]

N,M = map(int, input().split()) 
myMap = [[0 for j in range(M)] for i in range(N)] # 맵 정보 저장
visited = [[False for j in range(M)] for i in range(N)]

for i in range(N):
    myMap[i] = list(map(int, input().split()))

sNum = 1 # 섬 번호
sumlist = list([]) # 모든 섬 정보 이중 리스트
mlist = [] # 1개의 섬 정보 리스트

def addNode(i,j,queue): # 섬에 한 칸(노드)을 더해주는 함수
    myMap[i][j] = sNum
    visited[i][j] = True
    temp = [i, j]
    mlist.append(temp)
    queue.append(temp)

def BFS(i,j): # 같은 섬 인식하기
    queue = deque()
    mlist.clear()
    start = [i,j]
    queue.append(start)
    mlist.append(start)
    visited[i][j] - True
    myMap[i][j] = sNum

    while queue:
        r,c = queue.popleft()
        for d in range(4):
            tempR = dr[d]
            tempC = dc[d]
            while r+tempR>=0 and r+tempR<N and c+tempC>=0 and c+tempC<M:
                if not visited[r+tempR][c+tempC] and myMap[r+tempR][c+tempC] !=0:
                    addNode(r+tempR, c+tempC, queue)
                else:
                    break
                if tempR<0:
                    tempR-=1
                elif tempR>0:
                    tempR+=1
                elif tempC<0:
                    tempC-=1
                elif tempC>0:
                    tempC+=1
    return mlist

for i in range(N): # 섬 구분 작업 수행
    for j in range(M):
        if myMap[i][j] != 0 and not visited[i][j]:
            # 깊은 복사로 해야 주소를 공유하지 않음
            tempList = copy.deepcopy(BFS(i,j)) # BFS를 실행해 하나의 섬 정보를 가져오기
            sNum+=1 # 새로운 섬 넘저링
            sumlist.append(tempList) # 하나의 섬 정보를 sumlist에 추가

pq = PriorityQueue()

for now in sumlist: # 섬의 각 지점에서 만들 수 있는 모든 에지를 저장
    for temp in now:
        r = temp[0]
        c = temp[1]
        now_s = myMap[r][c]
        for d in range(4): # 4방향 검색
            tempR=dr[d]
            tempC=dc[d]
            blength = 0
            while r+tempR>=0 and r+tempR<N and c+tempC>=0 and c+tempC<M:
                # 같은 섬이면 에지를 만들 수 없음
                if myMap[r+tempR][c+tempC]==now_s:
                    break
                # 같은 섬도 아니고 바다도 아니면
                elif myMap[r+tempR][c+tempC]!=0:
                    if blength>1: # 다른 섬-> 길이가 1이상일 때 에지로 더하기
                        pq.put((blength, now_s, myMap[r+tempR][c+tempC]))
                    break
                else: # 바다이면 다리의 길이 연장
                    blength+=1
                if tempR<0:
                    tempR-=1
                elif tempR>0:
                    tempR+=1
                elif tempC<0:
                    tempC-=1
                elif tempC>0:
                    tempC+=1

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)
    if a!=b:
        parent[b]=a
                
parent= [0]*sNum

for i in range(len(parent)):
    parent[i]=i

useEdge = 0
result = 0

while pq.qsize()>0: # MST 수행
    v,s,e=pq.get()
    if find(s)!=find(e):
        union(s,e)
        result+=v
        useEdge+=1

if useEdge==sNum-2: # sNum이 실제 섬의 수보다 1크기 때문에 섬의 번호 표시를 위해 -1로 연산
    print(result)
else:
    print(-1)

• 지도의 정보를 2차원 리스트에 저장하고 섬으로 표시된 모든 점(>0)에서 BFS를 실행해 섬을 구분한다. 방문한 적이 없고 바다가 아닐 때 같은 섬으로 인식한다.
• 모든 섬에서 상하좌우로 다리를 지어 다른 섬으로 연결할 수 있는지 확인한다. 연결할 곳이 현재 섬이면 탐색 중단, 바다라면 탐색을 계속 수행한다. 다른 섬을 만났을 때 다리의 길이가 2이상이면 이 다리를 에지 리스트에 추가한다.
• 전 단계에서 수집한 모든 에지를 오름차순 정렬해 MST를 수행한다. 수행 후 사용한 에지의 합을 출력한다.

 

https://www.acmicpc.net/problem/1414

• 인접 행렬의 형태로 데이터가 들어오므로 MST가 가능한 형태로 변형한다.
• 먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다. 
• i==j인 경우 별도 에지로 저장하지 않고 나머지 위치의 값들을 i->j로 가는 에지로 생성 후 에지 리스트에 저장한다.

 

import sys
from queue import PriorityQueue
input = sys.stdin.readline

N = int(input())
pq = PriorityQueue()
sum = 0

for i in range(N):
    tempc = list(input())
    for j in range(N):
        temp = 0
        if 'a'<=tempc[j]<='z':
            temp=ord(tempc[j])-ord('a')+1
        elif 'A'<=tempc[j]<='Z':
            temp=ord(tempc[j])-ord('A')+27
        sum+=temp # 총 랜선의 길이 저장
        if i!=j and temp!=0:
            pq.put((temp, i, j)) # 정렬 순서를 고려하여 input 데이터 순서 설정

parent= [0]*N

for i in range(len(parent)):
    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)
    if a!=b:
        parent[b]=a

useEdge = 0
result = 0

while pq.qsize()>0: # MST 수행
    v,s,e=pq.get()
    if find(s)!=find(e):
        union(s,e)
        result+=v
        useEdge+=1

if useEdge==N-1:
    print(sum-result)
else:
    print(-1)

• 입력 데이터의 정보를 리스트에 저장한다. 입력으로 주어진 문자열을 숫자로 변환해 총합으로 저장한다. i!=j인 경우 에지 리스트에 저장한다.
• 저장된 에지리스트를 바탕으로 MST를 수행한다.
• MST의 결괏값이 최소한으로 필요한 랜선 길이이므로 처음 저장해 둔 랜선의 총합에서 MST의 결괏값을 뺀 값을 정답으로 출력한다. 이때 트리에서 사용한 에지 개수(useEdge)가 N-1인 경우 모든 컴퓨터를 연결할 수 없으므로 -1을 출력한다.

 

---

# 회고

 

그래프 끝!!

그래프는 너무 어려웡..이론도 어렵구 구현도 어렵다. 물리문제 푸는 기분이다.

물리도 알고 푸는 방법도 알지만 문제를 보고 적용을 못하는...개어려운 문제들...ㅜㅜ

 

중간중간 구현, 탐색 등 다양한 이론들도 함께 쓰여서 더 어렵당