위상정렬이 정말 쉽지가 않은 알고리즘인 것은 확실하다..
진입 / 진출 차수를 checking하면서 -1하며 queue 혹은 우선순위 큐인 힙에 저장하는 방식을 주로 활용하는 것 같다.
그보다 더 어려운 것은 위상정렬은 문제를 보고 위상정렬 문제인지 파악하기도 쉽지 않고,
파악하더라도 똑같은 방식이 아닌 유동적인 문제 풀이가 필요하므로 매우 고수준의 이해를 요한다.
어려운 문제를 리뷰하며 조금 더 확실하게 이해해 보자
BaekJun - # 1432 : 그래프 수정 (위상정렬)
방향 그래프의 연결성분을 행렬로 나타낸 행렬 그래프를 제시 한 뒤
더 높은 수의 정점이 더 높은 위상을 가지도록 변경하고 그 변경점을 출력하도록 하는 문제였다.
장장 5시간을 고민하며 코드를 구현해 나갔지만, 내 머리로는 도저히 멍청하고, 억지스러운 교체와 연결 성분 변경 작업이 진행됬다.
예를 들면 1 -> 4 -> 3 인 상황에서 높은수를 확인 한 후 부모가 나보다 낮다면 교체한다.
하지만 1의 부모는 4로 저장되있기 때문에 1의 부모를 변경해주기 위해 4는 자식 성분도 기억해야 하며
3의 부모는 없지만 4를 추가해줘야 하면서 동시에 자식을 1로 설정해줘야 하는 매우 말도 안되는 교체과정이 생겨버리는 것이다.
분명,, 이방법이 아닌데도 이 방법 말고 떠오르지가 않았다.
결국 다른 분의 포스팅을 보고 방법을 확인했다.
방법은 다음과 같았다.
이 문제를 해석하신 블로거 분이 올려놓은 풀이 방법이다.
0. 진출차선을 저장해 놓은 뒤,
1. 진출차선이 없는 정점을 큐에 삽입한다.
2-0. 진출차선에서 POP한 정점은 자신의 자식들의 진출차선을 -1하고
2-1. 자식중에 진출차선이 0이 되는 자식이 있다면 우선순위 큐에 넣어 준다.
3. 큐에서 POP 과정(2) 을 끝낼때 마다 최종 출력할 결과 리스트에 pop과정을 끝낸 정점 수의 인덱스에 n부터 내림차순으로 숫자를 기입한다.
처음엔 이 과정이 이해가 잘 안될 수 있지만 예제의 플로우를 이 방식에 대입해 보면 이해가 된다.
진출차선이 없다는 것은 가장 위상이 높다는 것이고,
그 인덱스에 원래 숫자 (위 과정을 통하면 처음의 3인 인덱스에 3이 있어야 함)가 있어야 하지만, 5를 기입함으로서 제일 높은 위상에 제일 높은 수가 대입되는 것이다.
이 풀이 방법을 생각하며 코드로 풀어내봤다.
from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
graph = {} # { 자식 : [부모1, ...] }
matrix = []
outdegree = [0 for _ in range(n+1)]
result = [0 for i in range(n)]
for _ in range(n):
matrix.append(list(map(int,sys.stdin.readline().strip())))
for i in range(n):
for j in range(n):
if matrix[i][j] == 1:
if not j+1 in graph:
graph[j+1] = [i+1]
else:
graph[j+1].append(i+1)
outdegree[i+1] += 1
def bfs_change(n):
heap =[]
heapq.heapify(heap)
for i in range(1,n+1):
if outdegree[i] == 0:
heapq.heappush(heap,i*(-1))
if not heap:
result[0] = 0
return
for x in range(n,0,-1):
now = (heapq.heappop(heap))*(-1)
if now in graph:
for son in graph[now]:
outdegree[son] -= 1
if outdegree[son] == 0:
heapq.heappush(heap,son*(-1))
result[now-1] = x
bfs_change(n)
if result[0] == 0:
print(-1)
else:
print(' '.join(list(map(str,result))))
print(' '.join(list(map(str,result))))큰수부터 차례대로 저장하기 위함, 그리고 모든 노드를 한번씩 결과 리스트에 저장하기 위하여 while 큐 대신
for문을 큰수부터 차례대로 result에 가장 위상이 높은 인덱스에 넣어주는 방식으로 풀었다.
Tries 알고리즘
알고리즘 공부 키워드 중에 Tries라는게 있길래 뭔지 공부하기 위해서 찾아봤다.
Tries는 문자열을 트리에 저장하고 효율적으로 탐색하기 위한 자료구조이다.
트리는 탐색하는데 걸리는 시간 복잡도가 O(logN) 이다.
근데 문자열은 노드를 탐색할 때, 문자열의 길이만큼 시간이 더 길어지므로, 문자열의 길이를 L이라고 한다면
O(LlogN)이 걸리는것이다.
그래서 문자열만 특별히 효율적으로 탐색하기 위해 Tries 자료구조를 만들었다.
시작 root는 모든 알파벳이 같은 문자로 시작할 수 없기 때문에 비워두고
바로밑에 cat이라는 문자열을 저장한다면
C를 저장하고
그 정점의 아들 노드에 A
그 아들 노드에 T를 저장하는 구조이다.
이런식으로 문자열을 저장하면 삽입은 트리구조와 동일하고,
문자를 탐색할때는 O(L)이 소요된다. !
매우 시간이 단축됨을 알 수 있다.
플로이드 워셜 알고리즘
플로이드 워셜은 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다.
방법은 다음과 같다.
1. N개의 정점이 있다면 먼저 바로 옆에 붙어있지 않아서 갈 수 없는 정점을 제외하고 가중치를 인접 그래프 표현법에 기재한다.
2. N번의 라운드를 진행하는데, k 라운드 시 k번의 노드를 중간 다리로 선정하여, 만약 중간다리를 거치고 간다면 갈 수 있는 곳 까지 가중치를 합산하여 기록한다.
3. N번의 라운드가 모두 끝나면 가중치가 가장 적은 비용으로 저장되어있다.
워셜 알고리즘은 O(N^3)의 시간복잡도로 매우 성능이 좋지 않아 그래프의 크기가 작을때만 사용한다고 한다.
플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장해서 점화식을 이용해서 최단 거리 정보를 추출해 내기 때문에 다이나믹 프로그래밍 유형에 속한다고 한다.
N^3의 시간복잡도는 매우 낮은 성능을 가진다는 것을 의미한다.
이런데도 이 알고리즘을 공부하는 이유는
이방법이 매우 간편하기 때문이다.
따라서 N의 최대값이 100보다 작다면 이 방식으로 결과를 쉽게 도출해 낼 수 있다.
'Jungle' 카테고리의 다른 글
| [TIL][Krafton Jungle] 2주차 - (7) : 누적 합과 스위핑 (1) | 2023.10.25 |
|---|---|
| [TIL][Krafton Jungle] 2주차 - (6) : 잡다한 알고리즘 및 CS 공부 (1) | 2023.10.24 |
| [TIL][Krafton Jungle] 2주차 - (4) : 위상정렬 알고리즘 (4) | 2023.10.22 |
| [TIL][Krafton Jungle] 2주차 - (3) : DFS 알고리즘 공부 (5) | 2023.10.21 |
| [TIL][Krafton Jungle] 2주차 - (2) : BFS 알고리즘 공부 (1) | 2023.10.20 |