[TIL] Algorithm - 위상 정렬 + 플로이드-워셜

728x90

1. 그래프 문제 풀이

1. 2573번 - 빙산

▶ BFS를 이용한 풀이

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 빙산 녹이는 함수
def melting() :
    change = []
    for i in range(1, N-1) :
        for j in range(1, M-1) :
            if iceberg[i][j] != 0 :
                sea = 0 # 현재 위치에서 0과 맞닿아 있는 개수
                for k in range(4) :
                    nx, ny = i + dx[k], j + dy[k]
                    if 0 <= nx < N and 0 <= ny < M and iceberg[nx][ny] == 0 :
                        sea += 1
                if iceberg[i][j] - sea > 0 : # 아직 녹아서 사라지지 않을 경우
                    iceberg[i][j] = iceberg[i][j] - sea
                else : # 녹아서 사라질 경우 후에 계산을 위해 나중에 변경
                    change.append((i, j))
    for x, y in change : # 사라질 부분 0으로 변경
        iceberg[x][y] = 0

# 빙산 덩어리 탐색을 위한 BFS 함수
def bfs(s, e) :
    queue = deque()
    
    queue.append((s, e))
    visited[s][e] = 1
    
    while queue :
        xx, yy = queue.popleft()
        for i in range(4) :
            nx, ny = xx + dx[i], yy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and iceberg[nx][ny] != 0 :
                visited[nx][ny] = 1
                queue.append((nx, ny))

day = 0
while True :
    visited = [[0] * M for _ in range(N)]
    count = 0 # 현재 빙산 덩어리의 개수
    for i in range(N) :
        for j in range(M) :
            if iceberg[i][j] != 0 and visited[i][j] == 0:
                bfs(i, j)
                count += 1
    if count > 1 : # 이미 나눠져 있다면
        print(day)
        break
    elif count == 0 : # 이미 녹아서 사라졌다면
        print(0)
        break
    
    # 아직 한덩어리라면 더 녹여본다.
    melting()
    day += 1

▶ DFS를 이용한 풀이

import sys

N, M = map(int, sys.stdin.readline().split())

iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 빙산 녹이는 함수
def melting() :
    change = []
    for i in range(1, N-1) :
        for j in range(1, M-1) :
            if iceberg[i][j] != 0 :
                sea = 0 # 현재 위치에서 0과 맞닿아 있는 개수
                for k in range(4) :
                    nx, ny = i + dx[k], j + dy[k]
                    if 0 <= nx < N and 0 <= ny < M and iceberg[nx][ny] == 0 :
                        sea += 1
                if iceberg[i][j] - sea > 0 : # 아직 녹아서 사라지지 않을 경우
                    iceberg[i][j] = iceberg[i][j] - sea
                else : # 녹아서 사라질 경우 후에 계산을 위해 나중에 변경
                    change.append((i, j))
    for x, y in change : # 사라질 부분 0으로 변경
        iceberg[x][y] = 0

# 빙산 덩이리 탐색을 위한 DFS 함수
def dfs(s, e) :
    visited[s][e] = 1
    stack = [(s, e)]
    
    while stack :
        xx, yy = stack.pop()
        for i in range(4) :
            nx, ny = xx + dx[i], yy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and iceberg[nx][ny] != 0:
                visited[nx][ny] = 1
                stack.append((nx, ny))

day = 0
while True :
    visited = [[0] * M for _ in range(N)]
    count = 0 # 현재 빙산 덩어리의 개수
    for i in range(1, N-1) :
        for j in range(1, M-1) :
            if iceberg[i][j] != 0 and visited[i][j] == 0:
                dfs(i, j)
                count += 1
    if count > 1 : # 이미 나눠져 있다면
        print(day)
        break
    elif count == 0 : # 이미 녹아서 사라졌다면
        print(0)
        break
    
    # 아직 한덩어리라면 더 녹여본다.
    melting()
    day += 1

솔직히 이 문제를 처음 풀려고 할 때 빙산을 녹일 때 BFS, 빙산 덩어리를 찾을 때 DFS를 사용하여 구현하려고 했다.
모든 테스트케이스를 잘 통과한 듯 했지만 백준에서는 틀렸다 나와서 결국 블로그를 참고해서 풀었다.

BFS 풀이 참고 : https://jae-eun-ai.tistory.com/8
DFS 풀이 참고 : https://guccin.tistory.com/107

이번에는 작성한 풀이는 모두 python3로 돌아가긴하지만 시간도 오래 걸리고 메모리도 꽤 사용한다.
아마 melting 함수에서 많은 시간과 메모리를 사용하는 것 같은데 새로운 방식을 찾아봐야겠다.
다음에는 시간을 더 줄이는 방법을 통해 풀어보도록 해야겠다.

2. 2617번 - 구슬 찾기

1. DFS를 이용한 풀이

import sys

N, M = map(int, sys.stdin.readline().split())

arr = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

heavy = [[]for _ in range(N)]
light = [[]for _ in range(N)]

mid = (N+1) // 2 # 중앙값의 인덱스

# 각각의 구슬이 무거운, 가변운 측정 결과 저장
for x, y in arr :
    # x보다 가벼운 구슬들
    light[x-1].append(y-1)
    # y보다 무거운 구슬들
    heavy[y-1].append(x-1)

def dfs(v, weight) :
    visited = [0] * N
    stack = []
    
    visited[v] = 1
    stack.extend(weight[v])
    count = 0
    
    while stack :
        current = stack.pop()
        if visited[current] == 0 :
            count += 1
            stack.extend(weight[current])
            visited[current] = 1
    return count

result = 0
for i in range(N) :
    h = dfs(i, heavy) # 현재 구슬보다 무거운 구슬 개수
    l = dfs(i, light) # 현재 구슬보다 무겁지 않은 구슬 개수
    if h >= mid or l >= mid :
        result += 1
print(result)

처음에는 하나의 리스트에 넣어서 함께 DFS를 탐색했다. 기본적으로 주어진 경우들은 다 결과를 도출했는데 틀렸다.
생각해보니까 탐색 순서가 다를텐데 너무 쉽게 생각한듯..
그래서 두개의 리스트로 나눠서 현재 구슬보다 무거운 구슬의 개수, 가벼운 구슬의 개수를 구해서 비교했다.

2. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

가중 그래프에서 최단 경로를 찾는 알고리즘
모든 정점 쌍 간의 최단 경로의 길이를 찾는다.
https://chanhuiseok.github.io/posts/algo-50/
shortestPath(i, j, l) : i → j 로 가는 최단 경로를 찾는다.
- k를 통과하지 않는 경로 = shortestPath(i, j, k-1)
- k를 통과하는 경로 = shortestPath(i, k, k-1) + shortestPath(k, j, k-1)
- 위의 두가지 경우 중 작은 경우를 선택한다.

https://ko.wikipedia.org/wiki/플로이드-워셜_알고리즘

import sys

N, M = map(int, sys.stdin.readline().split())
mid = (N+1) // 2 # 중앙값의 인덱스
marble = [[0] * N for _ in range(N)]
for _ in range(M) :
    x, y = map(int, sys.stdin.readline().split())
    # x가 y보다 무겁다.
    marble[x-1][y-1] = 1

# 플로이드-워셜 알고리즘
# 만약 무게를 i가 k보다 무겁고 k가 j보다 무겁다는 것을 알면
# i 는 j 보다 무겁다고 할 수 있다.
for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            if marble[i][k] and marble[k][j] :
                marble[i][j] = 1

result = 0
for i in range(N) :
    # i 보다 가벼운 구슬의 개수를 저장할 변수 left
    # i 보다 무거운 구슬의 개수를 저장할 변수 right
    left, right = 0, 0
    for j in range(N) :
        if i == j :
            continue
        elif marble[i][j] == 1 :
            left += 1
        elif marble[j][i] == 1 :
            right += 1
    if left >= mid or right >= mid :
        result += 1
print(result)

처음에는 왜 플로이드-워셜 알고리즘이 생각나는지 모르겠었는데 모든 구슬들의 관계를 살펴보고 이를 활용하면 간단하게 풀린다는 것을 알았다.

< 참고 > https://kspsd.tistory.com/15

2. 위상 정렬

1. 위상 정렬(Topological Sorting)

유향 그래프의 정점들의 변의 방향을 거스르지 않도록 나열하는 것
선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 이용
단, 위상 정렬이 성립하기 위해서는 비순환 방향 그래프(Directed Acyclic Graph, DAG)여야 한다.

어떤 DAG는 최소 하나의 위상 순서을 가지고 있다.
위상 순서(Topological Order) : 위상 정렬 과정에서 선택되는 정점의 순서
위상 순서에서 모든 간선은 오른쪽만 가리키게 된다.

진입 차수(In-Degree) : 한 정점이 수행되기 전에 먼저 수행되어야 할 정점의 개수 → BFS를 이용
진출 차수(Out-Degree) : 한 정점이 수행되고 난 후에 수행할 수 있는 정점의 개수 → DFS를 이용

2. In-Degree 방법(BFS)

모든 정점의 IN-Degree(진입차수)를 설정한다.
IN-Degree가 0이 정점은 방문한 것으로 표시하고 큐에 추가
while queue : 큐가 빌 때까지 실행
- x : queue.pop() 큐에 있는 정점 한 개를 뽑는다
- x와 인접한 모든 정점의 IN-Degree를 -1 감소
  - 만약 IN-Degree가 0이라면 큐에 추가
2252번 - 줄세우기 (BFS 풀이)

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N)]
inDegree = [0] * N

for _ in range(M) :
    x, y = map(int, sys.stdin.readline().split())
    graph[x-1].append(y-1)
    inDegree[y-1] += 1

def topologicalSort(d) :
    queue = deque()
    visited = [0] * N
    result = [] # 정렬 결과 저장
    
    # 진입 차수가 0인 정점 처리
    for i in range(N) :
        if d[i] == 0 :
            visited[i] = 1
            queue.append(i) 
            
    while queue :
        current = queue.popleft()
        result.append(current+1) # 정렬 결과 저장
        # 현재 정점에 연결된 정점의 차수 -1감소
        for i in graph[current] :
            if visited[i] == 0 and d[i]:
                d[i] -= 1
            if d[i] == 0 : # 정점의 진입차수가 0이되면 큐에 삽입하여 정렬 준비
                visited[i] = 1
                queue.append(i)
    print(*result)

topologicalSort(inDegree)

3. DFS를 이용한 방법

동작
- 임의의 방문하지 않은 정점을 잡고 DFS 수행하면서 스택에 쌓는다.
- 모든 정점을 방문할 때까지 위의 DFS 과정 수행
- 모든 정점을 방문했다면 스택에 담긴 정점 출력
DFS는 깊이 우선 탐색이다. 즉, 한 정점에서 DFS를 수행하면 말단 노드까지 내려간다.
그런데 말단 노드는 Out-Degree(진출차수)가 무조건 0이므로 가장 마지막에 수행되어야 한다.
2252번 - 줄세우기 (DFS 풀이)

import sys

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N)]

for _ in range(M) :
    x, y = map(int, sys.stdin.readline().split())
    graph[x-1].append(y-1)

def topologicalSort(v) :
    visited[v] = 1
    
    for i in graph[v] :
        if visited[i] == 0:
            topologicalSort(i)
    stack.append(v) # 현재 노드를 가장 마지막에 스택에 push하도록!

visited = [0] * N
stack = [] # 가장 마지막 말단노드부터 쌓이도록 해야한다.
for i in range(N) :
    if visited[i] == 0 :
        topologicalSort(i)

while stack : # 스택에서 꺼내는 순서가 위상 순서
    print(stack.pop()+1, end=' ')

< 참고 >
🔗 https://ko.wikipedia.org/wiki/위상정렬
🔗 https://yoongrammer.tistory.com/86
🔗 https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html
🔗 https://sorjfkrh5078.tistory.com/36

728x90

저작자표시

'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글

[TIL] Algorithm - 동적 프로그래밍 기본 (0)	2023.04.27
[TIL] 위상 정렬 문제 풀이 + Computer System2 (0)	2023.04.26
[TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) (0)	2023.04.24
[TIL] 그래프 문제 문제 풀이 (0)	2023.04.22
[TIL] Algorithm - 최소 신장 트리 + 그래프 기본 문제 풀이 (1)	2023.04.21

soo-note

[TIL] Algorithm - 위상 정렬 + 플로이드-워셜

1. 그래프 문제 풀이

1. 2573번 - 빙산

2. 2617번 - 구슬 찾기

2. 위상 정렬

1. 위상 정렬(Topological Sorting)

2. In-Degree 방법(BFS)

3. DFS를 이용한 방법

'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글

티스토리툴바

[TIL] Algorithm - 위상 정렬 + 플로이드-워셜

1. 그래프 문제 풀이

1. 2573번 - 빙산

2. 2617번 - 구슬 찾기

2. 위상 정렬

1. 위상 정렬(Topological Sorting)

2. In-Degree 방법(BFS)

3. DFS를 이용한 방법

'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글

관련글

티스토리툴바