🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.
플로이드 워셜 알고리즘 개요
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스타라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.
플로이드 워셜 알고리즘
각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
점화식은 다음과 같다
플로이드 워셜 알고리즘: 코드
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]
# 자기 자신에게 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
# 수행된 결과를 출력
for a in range(1, n+1):
for b in range(1, n+1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == INF:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()나의 문제 풀이들
# 문제 요약 :
# - 학생들에게 0 ~ n 번호 부여
# - 처음에는 학생들이 모두 다른 팀 : n+1 개의 팀 존재
# - 2개의 연산 :
# 1) 팀 합치기
# " 0 a b "
# 2) 같은 팀 여부 확인
# " 1 a b "
# > m 개의 연산, '같은 팀 여부 확인' 연산에 대한 연산 결과 출력
# 아이디어 :
# 1. n + 1 개의 빈 부모 테이블 생성 및 초기화
# 2. 팀 합치기 함수 생성
# 3. 부모 찾기 함수 생성
# + 같은 팀 여부 확인 함수 생성
# 4. 입력 받을 때 마다 " 0 / 1 " 확인해서 해당 함수 실행
# 5. 출력하기
# > "서로소 집합 자료구조, 경로 압축" 을 사용
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent, parent[x])
return x
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def same_team(parent, a, b):
if parent[a] == parent[b]:
print("YES")
else:
print("NO")
n, m = map(int, input().split()) # 입력받기
parent = [0] * (n+1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n+1):
parent[i] = i
for _ in range(m):
x, a, b = map(int, input().split())
if x == 0:
union_parent(parent, a, b)
else:
same_team(parent, a, b)# n개의 집, m개의 간선, 유지비 > 크루스칼 알고리즘 - 최소 신장 트리
# 2개의 분리된 마을로 분할
# 분리된 마을 안에 있는 집들은 모두 연결되어야 함
# 분리된 두 마을 사이에 있는 길들은 없앨 수 있음
# 나머지 길의 유지비의 합을 최소로 하고싶음
# 아이디어:
# 크루스칼 알고리즘으로 최소신장트리를 만든 후,
# 가장 비용이 큰 도로를 없애면 되는 문제
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
return
n, m = map(int, input().split())
parent = [0] * (n + 1)
edges = []
result = 0
for i in range(1, n+1):
parent[i]= i
for _ in range(m):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
last = cost
print(result - last)# 문제요약 :
# 선수강의를 들어야 해당 강의를 들을 수 있음 -> "위상정렬 알고리즘"
# 강의는 1 ~ N번의 번호를 가짐
# N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 출력
# "위상정렬 알고리즘 ?"
# - 정렬 알고리즘의 일종
# - 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용
# - 대표적인 예시로, 선수과목을 고려한 학습순서 설정
# - ✨ 진입차수 ✨ : 특정한 노드로 들어오는 간선의 개수를 의미
# - 큐를 이용함
# 1. 진입차수가 0인 모든 노드를 큐에 넣는다.
# 2, 큐가 빌 때까지 다음의 과정을 반복한다.
# 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
# 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
# > 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.
# 핵심 아이디어 :
# 각 강의에 대하여 인접한 노드를 확인하면서 인접한 노드에 대해
# 현재보다 강의 시간이 더 걸린 경우를 찾는다면, 해당 시간으로 결과 테이블 갱신
# deepcopy ?
# deepcopy는 객체를 복사할 때 해당 객체의 모든 요소와 중첩된 객체까지 모두 새로운 복사본을 생성하여 복사합니다.
# 따라서 원본과 복사본은 완전히 독립적인 데이터를 가지게 됩니다.
# result 리스트는 각 강의를 듣는 데 걸리는 최대 시간을 저장하는데,
# 이 정보는 time 리스트와 공유하지 않고 독립적으로 관리해야 합니다.
# 그래서 copy.deepcopy() 함수를 사용하여 time 리스트를 복사하고,
# 이 복사본을 result 리스트에 할당함으로써 두 리스트가 서로 영향을 미치지 않도록 보장합니다.
from collections import deque
import copy
n = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for _ in range(n + 1)]
# 각 강의 시간 정보를 담기 위한 리스트 0으로 초기화
time = [0] * (n + 1)
for i in range(1, n + 1):
data = list(map(int, input().split()))
time[i] = data[0] # 해당 노드에 시간 저장
for x in data[1: -1]: # 해당 강의의 선행 강의 목록이 저장
graph[x].append(i) # 선수과목이 x 이니, x -> i
# print(" graph[x]", x, graph[x])
indegree[i] += 1 # 진입 차수는 들어오는 노드 입장이므로, i
# print(" indegree[i] ", i, indegree[i] )
def topology_sort():
result = copy.deepcopy(time)
q = deque()
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, n+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
for i in graph[now]:
# print("result[i]", result[i])
# max(result에 업데이트된 인접 노드 시간, result에 업데이트된 현재 노드 시간 + 인접노드의 시간)
result[i] = max(result[i], result[now] + time[i])
# print(" result[now] + time[i]", result[now] + time[i])
# 해당 원소와 연결된 노드들의 진입차수에서 1뺴기
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
for r in result[1:]:
print(r)
topology_sort()# 문제 자체가 이해가 안됐던 문제
# 문제 요약 :
# 비행기가 도킹할 수 있는 최대 탑승구에 도킹해감
# 도킹했으면, 최대 도킹 수를 줄임
# 아이디어 :
# 가능한 큰 번호의 탑승구로 도킹을 수행
# > 탑승구 번호가 주어질 때,
# 최대한 큰 번호의 탑승구로 비행기를 보내는 것이 도킹할 수 있는 비행기 개수가 최대가 됨
# 도킹 = union
# 단, union 연산 시, 어떤 탑승구 번호로 연결해야 하는지는 풀이에서 임의대로 만들어 정보를 부여받은 탑승구 번호 기준으로 -1 만큼 작은 탑승구
# 즉, 왼쪽에 있는 탑승구 번호로 연결해야 하도록 Union 연산을 하는 것으로 가정했다.(이걸 어떻게 시험장에서 떠올리지..? OMG다 증말..)
# 그리고 항상 부모 테이블을 만들 때, 0번 루트 노드가 자동으로 생기는데, 해
# 당 문제에서는 특정 탑승구 번호를 부여받았을 때, find 연산을 수행해서 0번 루트노드이면 더 이상 도킹할 수 없다는 것으로 룰을 만들었다..
g = int(input())
p = int(input())
# 탑승구를 하나의 집합으로 간주하고 서로소 집합 알고리즘 활용
parent = [0] * (g+1)
for i in range(1, g+1):
parent[i] = i
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
count = 0
for _ in range(p):
data = find_parent(parent, int(input()))
# 만약 주어진 g_i값의 루트노드가 0이라면 더이상 탑승구에 들어갈 수 없고 운행 중지
if data == 0: # find_parent() 함수 넣으면 바로 첫번째 재귀함수 return이 반환되므로 재귀함수 == 0 조건은 안 됨!
break
# 루트노드가 0이 아니라면 주어진 주어진 탑승구 번호의 루트 노드와 루트 노드-1을 union연산
union_parent(parent, data, data-1)
count += 1
print(count)
차곡차곡