# 8-1. 그래프의 표현
2차원 리스트
- python에서 3행 4열 2차원 리스트를 생성할 때는 두가지 방법이 있다.
# 리스트에서 객체를 생성하는 방법
A = [[0 for col in range(4) for row in range(3)]
# 얕은 복사를 일으켜 생성하는 방법
# 이 방식은 선언 후 값을 변경하면 다른 원소의 값도 변경될 수 있다.
A = [[0]*4]*3
에지 리스트(edge list)
- 에지를 중심으로 그래프를 표현한다. 리스트에 출발 노드, 도착 노드(+가중치)를 저장하여 에지를 표현한다.
- 구현이 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 어렵다.
- 노드 사이의 최단 거리를 구하는 벨만-포드 혹은 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용한다.
인접 행렬(adjacency matrix)
- 2차원 리스트를 자료구조로 사용하여 그래프를 표현한다.
- 노드 중심으로 그래프를 표현한다. 노드가 5개인 경우, 5x5 인접 행렬로 그래프를 표현한다.
- 예를 들어, 가중치 그래프에 경우 2에서 5로 향하는 에지의 가중치를 2행 5열에 기록한다.
인접 리스트(adjacency list)
- 노드 개수만큼 리스트를 선언한 후, 문제의 조건에 맞게 input data를 저장한다.
- 가중치 X 그래프 : N번 노드와 연결되어 있는 노드를 리스트의 index N에 append한다.
- 가중치 O 그래프 : 가중치가 있는 경우 input data를 (도착 노드, 가중치)로 사용하여 시작노드 index N 리스트에 저장한다.
- 인접 리스트를 이용한 그래프 구현은 복잡하지만 에지 탐색과 공간 효율면에서 좋다.
- 특히 DFS, BFS에서 자주 사용된다.
https://www.acmicpc.net/problem/18352
import sys
from collections import deque
input = sys.stdin.readline
N, M, K, X = map(int, input().split()) # 노드의 수, 에지의 수, 목표 거리, 시작점
A = [[] for _ in range(N+1)]
answer = []
visited = [-1]*(N+1)
def BFS(v):
queue = deque()
queue.append(v)
visited[v]+=1
while queue:
now_node=queue.popleft()
for i in A[now_node]:
if visited[i]==-1:
visited[i]=visited[now_node]+1
queue.append(i)
for _ in range(M):
S,E=map(int, input().split())
A[S].append(E)
BFS(X)
for i in range(N+1):
if visited[i]==K: # 방문거리가 k인 경우
answer.append(i)
if not answer:
print(-1)
else:
answer.sort()
for i in answer:
print(i)- 인접 리스트로 도시와 도로 데이터의 그래프를 구현한다.
- BFS 알고리즘으로 탐색을 수행하며 각 도시로 가는 최단 거릿값을 방문 리스트에 저장한다.
- 탐색 종료 후 방문 거리가 K인 도시의 번호를 출력한다.
https://www.acmicpc.net/problem/1325
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int, input().split())
A = [[] for _ in range(N+1)]
answer = [0]*(N+1) # 정답 리스트
def BFS(v):
queue = deque()
queue.append(v)
visited[v]=True
while queue:
now_node=queue.popleft()
for i in A[now_node]:
if not visited[i]:
visited[i]=True
answer[i]+=1 # 신규 노드 인덱스의 정답 리스트값을 증가
queue.append(i)
for _ in range(M):
S, E = map(int, input().split())
A[S].append(E)
for i in range(1, N+1): # 모든 노드에서 BFS 실행
visited=[False]*(N+1)
BFS(i)
maxVal = 0
for i in range(1, N+1):
maxVal=max(maxVal, answer[i])
for i in range(1, N+1):
if maxVal==answer[i]:
print(i, end=' ')- 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프(A -> B)를 표현한다.
- 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행한다. 수행되는 동안 탐색되는 노드들의 신뢰도(answer 리스트)를 증가시킨다.
- 탐색 종료 후 신뢰도의 최댓값을 Max값으로 정하고, 신뢰도 리스트를 다시 탐색하며 Max값을 지니고 있는 노드를 오름차순 출력한다.
- 시간초과 남..
from collections import deque
import sys
input = sys.stdin.readline
# 입력
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
A, B = map(int, input().split())
graph[B].append(A) # B노드를 신뢰하는 노드 저장
# bfs
ans = []
for i in range(1, N+1):
visited = [False]*(N+1)
queue = deque([i])
visited[i] = True
cnt = 1
while queue:
x = queue.popleft()
for j in graph[x]:
if not visited[j]:
visited[j] = True
queue.append(j)
cnt += 1
ans.append(cnt)
max_cnt = max(ans)
for i in range(N):
if ans[i] == max_cnt:
print(i+1, end=" ")- 같은 BFS이긴 한데, 처음 풀이는 A->B로 저장을 했다면 두번 째 풀이는 B->A로 저장을 했다.
- 즉, 한번 BFS를 탐색할때 그 노드의 신뢰도를 바로 구할 수 있다.
https://www.acmicpc.net/problem/2251\
- A,B,C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각한다.
from collections import deque
# 두 리스트를이용하여 6가지 이동 케이스를 간편하게 정의할 수 있다.
# 여기에서 0,1,2는 각각 A,B,C 물통을 뜻한다.
# 예시 : index = 0의 경우 Sender[0]:0, Receiver[0]:1 이기 때문에 A->B 케이스를 뜻한다.
Sender = [0,0,1,1,2,2]
Receiver = [1,2,0,2,0,1]
now = list(map(int, input().split()))
visited=[[False for j in range(201)] for i in range(201)]
answer = [False]*201
def BFS():
queue = deque()
queue.append((0,0))
visited[0][0] = True
answer[now[2]] = True
while queue:
now_node = queue.popleft()
A = now_node[0]
B = now_node[1]
C = now[2]-A-B # C는 전체 물의 양에서 A와 B를 뺀 것
for k in range(6): # A->B, A->C, B->A, B->C, C->A, C->B
next = [A,B,C]
next[Receiver[k]] += next[Sender[k]]
next[Sender[k]]=0
if next[Receiver[k]] > now[Receiver[k]]: # 물이 넘칠 때
# 초과하는 만큼 다시 이전 물통에 넣어주기
next[Sender[k]] = next[Receiver[k]]-now[Receiver[k]]
next[Receiver[k]] = now[Receiver[k]] # 대상 물통 최대로 채우기
if not visited[next[0]][next[1]]: # A와 B의 물의 양으로 방문 리스트체크
visited[next[0]][next[1]] = True
queue.append((next[0], next[1]))
if next[0]==0: # A의 물의 양이 0일때 C의 물의 무게를 정답 변수에 저장
answer[next[2]] = True
BFS()
for i in range(len(answer)):
if answer[i]:
print(i, end = ' ')- 즉 처음 물통 A,B,C의 최소 출발 노드를 (0,0,now[2]번째 물통의 용량)으로 초기화한다.
- BFS를 수행한다.
- 노드에서 갈 수 있는 6개의 경우(A->B, A->C, B->A, B->C, C->A, C->B)에 관해 다음 노드(next)로 정해 큐에 추가한다. A,B,C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않는다.
- 각 경우는 Sender[k] -> Receiver[k]로 판단
- 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통(Receiver)이 넘칠 때는 초과하는 값만큼 보내는 물통(Sender)에 남긴다.
- 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 리스트에 출발한다.
- 정답 리스트를 오름차순으로 출력한다.
# 8-2. 유니온 파인드
유니온 파인드(Union-find)란?
- 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있다.
- union 연산 : 각 노드가 속한 집합을 1개로 합친다.
- find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환한다.
구현 방법
- 일반적으로 1차원 리스트를 이용한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 되며, 리스트는 자신의 인덱스 값으로 초기화한다.
- 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. 1, 4 노드를 연결할 때, 1을 대표 노드, 4는 자식 노드로 union 연산을 하면 리스트 [4]의 대표 노드를 1로 설정한다.
- find 연산으로 자신이 속한 집합의 대표 노드를 찾는다. find 연산은 그래프를 정돈하고 시간 복잡도 O(1) 줄인다.
- 대상 노드 리스트에 index값과 value값이 동일한지 확인한다.
- 동일하지 않으면 value값이 가리키는 index 위치로 이동한다.
- 이동 위치의 index값과 value값이 같을 때까지 위 과정을 반복한다.
- 대표 노드에 도달하면 재귀 함수를 빠져나오며 거치는 모든 노드값(value)을 대표 노드 값으로 변경한다.
https://www.acmicpc.net/problem/1717
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N,M = map(int, input().split())
parent = [0]*(N+1)
def find(a): # find 연산
if a==parent[a]:
return a
else:
parent[a]=find(parent[a]) # 재귀 형태로 구현 -> 경로 압축 부분
return parent[a]
def union(a,b): # union 연산 대표 노드끼리 합치기
a = find(a)
b = find(b)
if a!=b:
parent[b]=a
def checkSame(a,b): # 두 원소가 같은 집합에 속해 있는지 확인하는 함수
a = find(a)
b = find(b)
if a == b:
return True
return False
for i in range(0, N+1):
parent[i] = i
for i in range(M):
question, a, b = map(int, input().split())
if question==0:
union(a,b)
else:
if checkSame(a,b):
print("YES")
else:
print("NO")- 전형적인 유니온 파인드 문제.
- 각 노드 리스트 초기화 후, find 연산으로 특정 노드의 대표 노드를 찾고 union 연산으로 2개의 노드를 이용해 각 대표 노드를 찾아 연결한다.
https://www.acmicpc.net/problem/1976
N=int(input())
M=int(input())
dosi=[[0 for j in range(N+1)] for i in range(N+1)]
def find(a): # find 연산
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
for i in range(1, N+1): # 도시 연결 데이터 저장
dosi[i]=list(map(int, input().split()))
dosi[i].insert(0,0)
route=list(map(int, input().split())) # 여행 도시 정보 저장
route.insert(0,0)
parent=[0]*(N+1)
for i in range(1, N+1): # 대표 노드를 자기 자신으로 초기화
parent[i]=i
for i in range(1, N+1): # 인접 행렬에서 도시가 연결되어 있으면 union 실행
for j in range(1, N+1):
if dosi[i][j]==1:
union(i,j)
index = find(route[1])
isConnect=True
for i in range(2, len(route)):
if index != find(route[i]):
isConnect=False
break
if isConnect:
print("YES")
else:
print("NO")- 도시의 연결 유무를 유니온 파인드 연산을 이용해 해결한다.
- 도시와 여행 경로 데이터를 저장하고, 각 노드와 관련된 대표 노드 리스트의 값을 초기화 한다.
- 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결돼 있을 때 union 연산을 수행한다.
- 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 결과값을 출력한다.
https://www.acmicpc.net/problem/1043
- 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결한다. 이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산으로 확인 후 과장된 이야기를 할 수 있는지 판단한다.
N, M = map(int, input().split())
trueP=list(map(int, input().split())) # 진실을 아는 사람 저장
T = trueP[0]
del trueP[0]
result = 0
party = [[] for _ in range(M)]
def find(a): # find 연산
if a==parent[a]:
return a
else:
parent[a]=find(parent[a]) # 재귀 형태로 구현 -> 경로 압축 부분
return parent[a]
def union(a,b): # union 연산 대표 노드끼리 합치기
a = find(a)
b = find(b)
if a!=b:
parent[b]=a
def checkSame(a,b): # 두 원소가 같은 집합에 속해 있는지 확인하는 함수
a = find(a)
b = find(b)
if a == b:
return True
return False
for i in range(M):
party[i] = list(map(int, input().split())) # 파티 데이터 저장
del party[i][0]
parent = [0]*(N+1)
for i in range(N+1): # 대표 노드를 자기 자신으로 초기화
parent[i]=i
for i in range(M): # 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
firstPeople=party[i][0]
for j in range(1, len(party[i])):
union(firstPeople, party[i][j])
# 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음
for i in range(M):
isPossible=True
firstPeople=party[i][0]
for j in range(len(trueP)):
if find(firstPeople)==find(trueP[j]):
isPossible=False
break
if isPossible:
result+=1 # 모두 다르면 결과값 1 증가
print(result)- 진실을 아는 사람 데이터(trueP), 파티 데이터(party), 유니온 파인드를 위한 대표 노드 자료구조(parent)를 초기화 한다.
- union 연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만든다.
- find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다. 파티 사람 노드는 모두 연결돼 있으므로 아무 사람이나 지정해 find 연산을 수행할 수 있다.
- 모든 파티에 관해 과정 3을 반복한 후 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결과값을 증가시킨다.
# 8-3. 위상 정렬
위상 정렬(topology sort)이란?
- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
- 항상 같은 순서로 정렬되지 않고, 사이클이 없어야 한다.
- 시간 복잡도 : O(V+E)
위상 정렬 핵심 이론
- 진입 차수(자기 자신을 가리키는 에지의 개수) 리스트를 업데이트 한다.
- 집입 차수 리스트에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 리스트에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
- 인접 리스트를 기반으로 수행한다.
https://www.acmicpc.net/problem/2252
- 예제 출력과 다를 수 있다. 위상 정렬은 늘 같은 값을 보장하지 않고 출력 조건이 없으므로!
from collections import deque
N,M=map(int, input().split())
A = [[] for _ in range(N+1)]
indegree = [0]*(N+1) # 진입 차수 리스트
for i in range(M):
S, E = map(int, input().split())
A[S].append(E)
indegree[E]+=1 # 진입 차수 데이터 저장
queue = deque()
for i in range(1, N+1):
if indegree[i]==0:
queue.append(i)
while queue: # 위상 정렬 수행
now = queue.popleft()
print(now, end=' ')
for next in A[now]:
indegree[next]-=1
if indegree[next]==0:
queue.append(next)- 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만들 때 노듸 순서를 도출한다.
- 인접 리스트(A)에 노드 데이터를 저장하고, 진입 차수 배열값(indegree)을 덥데이트 한다.
- 위상 정렬을 수행한다.
- 진입 차수가 0인 노드를 큐에 저장한다.
- 큐에서 데이터를 뽑아와 해당 노드를 탐색 결과(now)에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
- 감소했을 때 진입 차수가 0이 되는 노드를 큐에 삽입한다.
- 큐가 빌 때까지 위 과정을 반복한다.
https://www.acmicpc.net/problem/1516
from collections import deque
N = int(input())
A = [[] for _ in range(N+1)]
indegree = [0]*(N+1) # 진입 차수 리스트
selfBuild = [0]*(N+1) # 자기 자신을 짓는데 걸리는 시간
for i in range(1, N+1):
inputList = list(map(int, input().split()))
selfBuild[i]=(inputList[0]) # 건물을 짓는 데 걸리는 시간
index = 1
while True: # 인접 리스트 만들기
preTemp = inputList[index]
index += 1
if preTemp==-1:
break
A[preTemp].append(i)
indegree[i]+=1 # 진입 차수 데이터 저장
queue = deque()
for i in range(1, N+1):
if indegree[i]==0:
queue.append(i)
result = [0]*(N+1)
while queue: # 위상 정렬 수행
now = queue.popleft()
for next in A[now]:
indegree[next] -=1
# 시간 업데이트
result[next] = max(result[next], result[now] + selfBuild[now])
if indegree[next]==0:
queue.append(next)
for i in range(1, N+1):
print(result[i]+selfBuild[i])- 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다. 즉, 각 건물을 노드라고 생각할 때 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 문제이다.
- 인접 리스트(A)로 그래프를 표현하고 선물의 생산 시간(selfBuild)을 따로 저장한다. 진입 차수 리스트와 정답 리스트를 초기화 한다.
- 위상 정렬을 실행하면서 각 건물을 짓는데 걸리는 최대 시간을 업데이트한다.
- max(현재 건물(노드)에 저장된 최대 시간, 이전 건물(노드)에 저장된 최대 시간+현재 건물(노드)에 저장된 최대 시간)
- 정답 리스트에 자기 건물을 짓는 데 걸리는 시간을 더한 후 정답 리스트를 차례대로 출력한다.
https://www.acmicpc.net/problem/1948
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
M = int(input())
A = [[] for _ in range(N+1)]
reverseA = [[] for _ in range(N+1)]
indegree = [0]*(N+1) # 진입 차수 리스트
for i in range(M):
S, E, V = map(int, input().split())
A[S].append((E,V))
reverseA[E].append((S,V)) # 역방향 에지 정보 저장
indegree[E]+=1 # 진입 차수 리스트 저장
startDosi, endDosi = map(int, input().split())
queue=deque()
queue.append(startDosi)
result = [0]*(N+1)
while queue: # 위상 정렬
now = queue.popleft()
for next in A[now]:
indegree[next[0]] -= 1
result[next[0]] = max(result[next[0]], result[now]+next[1])
if indegree[next[0]]==0:
queue.append(next[0])
resultCount = 0
visited = [False]*(N+1)
queue.clear()
queue.append(endDosi)
visited[endDosi]=True
while queue: # 위상 정렬 reverse 수행
now = queue.popleft()
for next in reverseA[now]:
# 1분도 쉬지 않는 도로 체크
if result[next[0]] + next[1] ==result[now]:
resultCount += 1
if not visited[next[0]]:
visited[next[0]] = True
queue.append(next[0])
print(result[endDosi])
print(resultCount)- 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다. 단, 1분도 쉬지 않고 달려야 하는 도로의 수를 구하기 위해 에지 뒤집기라는 아이디어가 필요하다.
- 인접 리스트에 노드 데이터를 저장하고, 진입 차수 리스트 값을 업데이트 한다. 이때 에지의 방향이 반대인 역방향 인접 리스트(reverseA)도 함께 저장한다.
- 시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로(result)를 저장한다.
- 도착 도시에서 역방향으로 위상 정렬을 수행한다. 이때 "이 도시의 임계 경로 값+ 도로 시간(에지)==이전 도시의 임계 경로값"일 경우에는 이 도로를 1분도 쉬지 않고 달려야 하는 도로로 카운팅 하고, 이 도시를 큐에 삽입한다.
- 도착 도시의 임계 경로 값과 1분도 쉬지 않도 달려야 하는 도로의 수를 출력한다.
- 어렵다! 플래티넘 문제니까 당연하지만...엄청 어렵다 나중에 다시 풀어봐야 할듯
# 8-4. 다익스트라
다익스트라(dijkstra)란?
- 그래프에서 최단 거리를 구하는 알고리즘
- 에지는 모두 양수이며, 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 사용한다.
- 시간 복잡도 : O(ElogV)
다익스트라 핵심 이론
- 인접 리스트로 그래프를 구현한다. input 데이터 자료형은 (노드, 가중치)와 같은 형태로 선언한다.
- 최단 거리 리스트를 만들고, 출발 노드는 0, 이외의 노드는 무한(적당히 큰 값)으로 초기화 한다.
- 최단 거리 리스트에서 현재 값이 가장 작은 노드를 고른다. 시작은 0인 출발 노드.
- 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 인접 리스트를 참고하여 현재 선택된 노드의 에지들을 탐색하고, 연결 노드의 최단 거리 리스트는 두 값 중 더 작은 값으로 업데이트 한다.
- Min(선택 노드의 최단 거리 리스트의 값+에지 가중치, 연결 노드의 최단 거리 리스트의 값)
- 위 과정을 반복하여 최단 거리 리스트를 완성한다.
https://www.acmicpc.net/problem/1753
import sys
from collections import deque
from queue import PriorityQueue
V, E = map(int, input().split())
K = int(input())
distance = [sys.maxsize]*(V+1)
visited = [False]*(V+1)
myList=[[] for _ in range(V+1)]
q = PriorityQueue()
for _ in range(E):
u,v,w = map(int, input().split()) # 가중치가 있는 인접 리스트를 저장
myList[u].append((v,w))
q.put((0,K)) # K를 시작점으로 설정
distance[K] = 0
while q.qsize()>0:
current=q.get()
c_v = current[1]
if visited[c_v]:
continue
visited[c_v] = True
for tmp in myList[c_v]:
next=tmp[0]
value=tmp[1]
if distance[next] > distance[c_v]+value: # 최소 거리로 업데이트
distance[next]=distance[c_v]+value
# 가중치가 정렬 기준으로 순서를 가중치, 목표 노드 순으로 우선순위 큐 설정
q.put((distance[next], next))
for i in range(1, V+1):
if visited[i]:
print(distance[i])
else:
print("INF")- 인접 리스트(myList)에 노드를 저장하고 거리 리스트(distance)를 초기화 한다.
- 최초 시작점을 우선순위 큐에 삽입하고(q.put((0,K))) 다음 과정에 따라 알고리즘을 수행한다.
- 거리 리스트에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다. 즉, 우선순위 큐에서 데이터를 뽑아온다.(current=q.get())
- 해당 노드와 연결된 노드들의 최단 거리값을 다음 공식을 이용해 업데이트 한다.
- 연결 노드 거리 리스트 값보다 건택 노드의 거리 리스트 값+에지 가중치가 더 작은 경우 업데이트, 업데이트가 수행되는 경우 연결 노드를 우선순위 큐에 삽입한다.
- 큐가 빌 때까지 위 과정을 반복한다.
- 완성된 거리 리스트의 값을 출력한다.
- 근데 이 풀이는 시간초과가 난다...
import heapq
import sys
input=sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q= []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
#현재 노드와 연결된 인접 노드 확인
for i in graph[now]:
cost =dist+ i[1]
if cost < distance[i[0]] :
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
#V == 5일 때 1~5까지 노드가 있는거임.
V, E = map(int,input().split())
snode = int(input()) #시작 노드
graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1) #최단 거리 테이블
#연결 정보 입력
for _ in range(E):
u,v,w = map(int,input().split())
graph[u].append((v,w))
dijkstra(snode)
#i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
for i in range(1,V+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])- 실제 개발에서는 차이가 있지만, 코딩테스트에서는 priorityqueue와 heapq가 큰 차이가 없다. 따라서 속도가 더 빠른 heapq를 이용하도록 하자.
https://www.acmicpc.net/problem/1916
import sys
from queue import PriorityQueue
input = sys.stdin.readline
N = int(input())
M = int(input())
myList = [[] for _ in range(N+1)]
dist = [sys.maxsize]*(N+1)
visit = [False]*(N+1)
for _ in range(M):
start, end, weight = map(int, input().split())
myList[start].append((end, weight))
start_index, end_index = map(int, input().split())
def dijkstra(start, end):
pq=PriorityQueue()
pq.put((0, start))
# 우선순위에 데이터를 최단 거리, 노드 순으로 삽입
dist[start] = 0
while pq.qsize() > 0:
nownode = pq.get()
now = nownode[1]
if not visit[now]:
visit[now]=True
for n in myList[now]:
if not visit[n[0]] and dist[n[0]] > dist[now] + n[1]:
dist[n[0]] = dist[now]+n[1]
pq.put((dist[n[0]], n[0]))
return dist[end]
print(dijkstra(start_index, end_index))- 주어진 데이터로 그래프를 만든다. 도시는 노드, 도시 간 버스 비용은 에지로 나타낸다.
- 도시 개수 N의 크기만큼 인접 리스트의 크기를 설정한다. input 데이터는 (목표 노드, 가중치) 형태로 설정한다. 버스 개수 M의 크기만큼 반복문을 돌명서 그래프를 인접 리스트에 저장한다.
- 다익스트라 알고리즘을 수행 후 최단 거리 리스트가 완성되면 정답을 출력한다.
https://www.acmicpc.net/problem/1854
import sys
import heapq
input = sys.stdin.readline
N, M, K = map(int, input().split())
W = [[] for _ in range(N+1)]
# 거리 리스트를 충분히 큰 값으로 초기화
distance = [[sys.maxsize]*K for _ in range(N+1)]
for _ in range(M):
a,b,c = map(int, input().split())
W[a].append((b,c))
pq = [(0,1)] # 가중치 우선이기 때문에 가중치 목표 노드 순서로 저장
distance[1][0] = 0
while pq: # 변형된 다익스트라 수행
cost, node = heapq.heappop(pq)
for nNode, nCost in W[node]:
sCost = cost+nCost
if distance[nNode][K-1]>sCost:
distance[nNode][K-1]=sCost
distance[nNode].sort()
heapq.heappush(pq, [sCost, nNode])
for i in range(1, N+1):
if distance[i][K-1] == sys.maxsize:
print(-1)
else:
print(distance[i][K-1])- 최단 경로를 표현하는 리스트를 K개의 row를 갖는 2차원 리스트의 형태로 변경한다. 이렇게 하면 최단 경로와 최단 경로~K번째 최단 경로를 표현할 수 있다.
- 기존 다익스트라 로직에서 사용한 노드를 방문 리스트에 체크해 두고 다음 도착 시 해당 노드를 다시 사용하지 않도록 설정하는 부분은 삭데를 해야 한다. K번째 경로를 찾기 위해서는 노드를 여러 번 쓰는 경우가 생기기 때문이다.
- 주어진 예제 데이터를 기반으로 그래프를 그린다. 도시는 노드로, 도로는 에지로 나타낸다.
- 변수 선언 후 그래프 데이터를 받는 부분은 모두 다익스트라 알고리즘 준비 과정과 동일하다.
- 최단 거리 리스트를 1차원이 아닌 K개의 row를 갖는 2차원 리스트로 선언한다.
- 우선순위 큐에서 연결된 노드와 가중치 데이터를 가져온다.
- 연결 노드의 K번째 경로와 신규 경로를 비교해 신규 경로가 더 작을 떄 업데이트 한다. 이때 경로가 업데이트 되는 경우 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가한다.
- 위 과정을 우선순위 큐가 비워질 떄까지 방문한다.
- 최단 거리 리스트를 탐색하면서 K번째 경로가 무한대면 -1을 출력하고, 그외에는 해당 경로 값을 출력한다.
- 노드 데이터를 저장하는 객체 형식을 우선순위 큐(heapq)로 선언하여 새로운 노드가 삽입됐을 때 별도의 정렬을 해주지 않아도 된다!
# 회고
그래프 어렵다...
이론은 아는데 응용이 넘 어렵다.
난 DFS가 좋은데 BFS도 많이 풀어봐야지..
'코딩테스트' 카테고리의 다른 글
| [Python] 트리 (0) | 2024.05.17 |
|---|---|
| [Python] 그래프(2) (0) | 2024.05.12 |
| [Python] 그리디 문제 풀이 정리(2) (0) | 2024.05.07 |
| [Python] 그리디 문제 풀이 정리 (0) | 2024.05.04 |
| [Python] 정수론 (1) | 2024.05.02 |
