최단 경로 알고리즘

Yunes·2023년 12월 13일
다익스트라 최단 경로스터디이것이 코딩 테스트다 with 파이썬코딩테스트플로이드 워셜 최단 경로
0

알고리즘 및 코딩테스트

목록 보기
21/23
post-thumbnail

서론

백준 알고리즘 스터디 1기 2023.10.09 ~ 2023.12.03 (8주) 가 끝나고 이번주부터 2기를 시작했다. 2023.10.11 ~ 2024.02.04 (8주 예정)

1기때 다루지 못했던 자료구조나 아니면 다뤄봤지만 더 연습이 필요할 것 같은 주제들을 선정하여 8주간 알고리즘 공부를 집중적으로 하려고 한다.

1기에 이어 2기 역시 인프런 스터디 커뮤니티를 통해 인원들을 모집했고 이런 스터디에 관심이 여전히 많다는 점을 알 수 있었다. 모르는 분들을 모집하여 하다보니 과연 스터디원 모두가 만족하는 스터디를 운영하려면 어떤 점을 고려해야 하는지 항상 고민이 든다..

아무튼 이번주차 주제는 최단경로다.

아직까지 한번도 풀어보지 못했던 유형이라 반드시 한번 다루고 싶었던 주제였다. 그러니 본 포스팅에 관련 내용을 정리하고자 한다.

다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘 은 그래프에 여러 개의 노드가 있을 때 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다.

알고리즘의 원리
1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신
5. 3~4 번 과정 반복

다익스트라 최단 경로 알고리즘의 특징

  • 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 경로 정보를 항상 1차원 리스트에 저장하여 리스트를 갱신

만약 방문하지 않은 노드중 최단 거리가 가장 짧은 노드를 O(n) 으로 매번 탐색한다면 시간복잡도 측면에서 좋지 않습니다.
이 부분을 우선순위 큐를 통해 O(logn) 으로 줄일 수 있다.

백준 18352 특정 거리의 도시 찾기 문제

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

도시들중 특정 도시를 선정하여 해당 도시로부터 특정 거리에 있는 다른 도시들을 찾는 문제다.

최단경로를 통해 풀어야 한다는 것을 알 수 있고 이때 특정 도시로부터 특정 거리만큼의 최단 경로에 존재하는 도시들을 찾아야 하니 다익스트라 알고리즘을 사용해서 풀 수 있다. (다른 풀이도 존재한다.)

  1. 초기 설정

최단 경로 알고리즘 문제를 풀기 위해 최단 거리를 갱신할 딕셔너리 answer 와 각 노드별 연결 관계를 나타낼 graph 를 생성한다.

스크린샷 2023-12-12 오후 8 32 01

  1. 다익스트라 알고리즘
  • 우선순위 큐에 튜플 형식으로 현재 노드에서 (거리, 다음 노드) 형식으로 큐에 넣는다.
  • 시작 노드에서 시작 노드까지는 항상 0이다.
  • 만약 우선순위 큐에 노드가 남아있다면 하나씩 꺼내서 현재 가리키고 있는 노드와 해당 노드까지의 거리를 구한다.
  • 만약 이렇게 구한 거리가 기존 answer 의 거리보다 크면 갱신하지 않는다.
  • 현재 노드에서 갈 수 있는 모든 노드까지 반복해서 탐색할때 거리는 1씩 늘어나는데 이 거리가 기존 answer 에 기록한 거리보다 짧다면 최단 경로를 갱신하고 갱신할 때마다 우선순위 큐에 해당 (갱신된 거리, 다음 노드) 형식의 튜플을 넣는다.
  • 거리가 동일하다면 노드번호가 작은 경우를 먼저 탐색한다.

항상 현재 시작 노드로부터 최단 거리에 있는 노드를 우선순위 큐에서 뽑아 최단 경로를 갱신한다.

스크린샷 2023-12-12 오후 8 32 17

스크린샷 2023-12-12 오후 8 32 31

스크린샷 2023-12-12 오후 8 32 46

최단 경로를 구했으니 이중에서 원래 원했던 K 거리만큼의 거리 내에 있는 모든 노드를 출력한다.

전체 코드

import heapq
import sys 
input = sys.stdin.readline
INF = int(1e9)

N, M, K, X = map(int, input().split()) # N : 도시의 개수, M : 도로의 개수, K : 거리 정보, X : 출발 도시의 번호

# 최단 거리를 기록할 answer
answer = {node: INF for node in range(1, N + 1)}

# 연결 리스트 graph
graph = [[] for i in range(N + 1)]
for _ in range(M):
  A, B = map(int, input().split())
  graph[A].append(B) # A 에서 B 로 가는 경로가 존재

def dijkstra(start):
  que = []
  heapq.heappush(que, (0, start)) # 우선순위 큐 que 에 시작노드 start 까지의 최단 거리는 0이다.
  answer[start] = 0
  while que:
    dist, now = heapq.heappop(que) # que 에 넣은 튜플 (dist, now) dist 는 거리, now 는 노드
    if answer[now] < dist: # 갱신하지 않는 경우
      continue
    for next in graph[now]: # 현재 노드 now 에서 갈 수 있는 노드 next
      new_dist = dist + 1
      if new_dist < answer[next]:
        answer[next] = new_dist
        heapq.heappush(que, (new_dist, next))

dijkstra(X)

if K not in answer.values():
  print(-1)
else:
  for i in range(1, N + 1):
    if answer[i] == K:
      print(i)

플로이드 워셜 알고리즘

다익스트라 알고리즘이 한 지점에서 다른 특정 지점까지의 최단 경로를 구할때 사용한다면
플로이드 워셜 최단경로 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.

단, 성능이 그리 좋은 알고리즘은 아닌 것 같다. 최단경로를 갱신하려면 O(N^3) 의 시간복잡도가 필요하다.

즉, 플로이드 워셜 알고리즘은 다익스트라 알고리즘에서 한 지점에서 특정 지점까지의 최단 경로를 구할 때 우선순위 큐 대신 직접 연결되는 경로와 한다리 거쳐서 연결되는 겨올 사이의 거리 / 비용등을 비교하는 플로이드 워셜 알고리즘을 적용한다는 차이가 있다.

백준 11403번 경로 찾기 문제

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

이 문제는 모든 지점에서 다른 모든 지점으로 연결되는 경로의 존재 유무를 파악하는 문제다.

이런 경우 간단하게 플로이드 워셜 알고리즘을 적용해서 풀 수 있다.

풀이코드

1) 플로이드 워셜 알고리즘

# 플로이드 - 워셜 알고리즘
import sys 
input = sys.stdin.readline
INF = int(1e9)

N = int(input()) # N : 정점의 개수

graph = [[INF] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
  info = map(int, input().split())
  for j, val in enumerate(info):
    if val == 1:
      graph[i][j + 1] = 1

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):
    if graph[a][b] != INF:
      print(1, end=' ')
    else:
      print(0, end=' ')
  print()

2) 다익스트라 알고리즘

import heapq
import sys 
input = sys.stdin.readline
INF = int(1e9)

N = int(input()) # N : 정점의 개수

graph = [[] for _ in range(N + 1)]

for i in range(1, N + 1):
  info = map(int, input().split())
  graph[i].extend([j + 1 for j, val in enumerate(info) if val == 1])

def dijkstra(start, answer):
  que = []
  heapq.heappush(que, (0, start)) # 우선순위 큐 que 에 시작노드 start 까지의 최단 거리는 0이다.
  while que:
    dist, now = heapq.heappop(que) # que 에 넣은 튜플 (dist, now) dist 는 거리, now 는 노드
    if answer[now] < dist: # 갱신하지 않는 경우
      continue
    for next in graph[now]: # 현재 노드 now 에서 갈 수 있는 노드 next
      new_dist = dist + 1
      if new_dist < answer[next]:
        answer[next] = new_dist
        heapq.heappush(que, (new_dist, next))
  return answer

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

for i in range(1, N + 1):
  answer = {node: INF for node in range(1, N + 1)}
  now = dijkstra(i, answer)

  for j, val in enumerate(now.values()):
    if val != INF:
      matrix[i - 1][j] = 1

for row in matrix:
  for col in row:
    print(col, end=' ')
  print()

결과를 보면 플로이드 워셜이 O(N^3) 의 시간복잡도가 반드시 필요해서 다익스트라를 이용한 풀이보다 훨씬 시간이 더 많이 소요되는 모습을 볼 수 있다.

백준 1058번 친구 문제

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

이 문제는 한다리 혹은 두다리 거쳐 친구로 연결된 관계인 2-친구가 최대인 2-친구를 구하라는 문제이다.

마찬가지로 최단경로를 구하되, 그 거리가 1 또는 2인 경우가 가장 많을때 한 친구에게 2-친구가 최대 몇개가 존재하는지 찾아야 한다.

한 지점이 아니라 모든 지점에서 비교해야 하니 다익스트라보다 플로이드 워셜 알고리즘이 더 적합해 보였다.

플로이드 워셜 알고리즘

  1. 아직 친구관계가 몇 단계에 걸쳐 존재하는지 모르는 경우 완전히 단절된 경우 무한의 값을 할당한다. 이겨서는 int(1e9) 의 값을 할당했다.
INF = int(1e9)
N = int(input()) # N : 사람의 수
graph = [[INF] * (N + 1) for _ in range(N + 1)]

인덱스와 사람을 동일하게 보기 위해 앞에 1개의 의미없는 공간을 할당했습니다.

  1. 친구관계를 확인하기 위해 직접적인 친구관계의 경우 graph 에서 값을 INF -> 1 로 값을 변경한다.
# 친구관계 확인
for i in range(1, N + 1):
  info = list(input().rstrip())
  for j, val in enumerate(info):
    if val == 'Y':
      graph[i][j + 1] = 1
  1. 자기 자신과는 친구가 아닌 점을 반영한다.
# 자신과는 친구가 아니다.
for a in range(1, N + 1):
  for b in range(1, N + 1):
    if a == b:
      graph[a][b] = 0
  1. 플로이드 - 워셜 알고리즘은 직접적인 연결보다 한다리 걸쳐서 가는것의 거리 / 비용이 더 적을 경우 갱신하는 알고리즘이라 O(N^3) 의 시간복잡도로 탐색한다.
# 플로이드 - 워셜
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])
  1. 결과적으로 갱신된 graph 의 row 1 ~ N + 1, col 1 ~ N + 1 범위에서 1 또는 2의 값을 갖는다면 2-친구를 만족하는 경우이니 최대의 2-친구를 갱신한다.
for a in range(1, N + 1):
  count = 0
  for b in range(1, N + 1):
    if graph[a][b] == 1 or graph[a][b] == 2:
      count += 1
    if count > max_two_friend:
      max_two_friend = count

풀이코드

import sys 
input = sys.stdin.readline
INF = int(1e9)

N = int(input()) # N : 사람의 수
graph = [[INF] * (N + 1) for _ in range(N + 1)]
max_two_friend = 0

# 친구관계 확인
for i in range(1, N + 1):
  info = list(input().rstrip())
  for j, val in enumerate(info):
    if val == 'Y':
      graph[i][j + 1] = 1

# 자신과는 친구가 아니다.
for a in range(1, N + 1):
  for b in range(1, N + 1):
    if a == b:
      graph[a][b] = 0

# 플로이드 - 워셜
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):
  count = 0
  for b in range(1, N + 1):
    if graph[a][b] == 1 or graph[a][b] == 2:
      count += 1
    if count > max_two_friend:
      max_two_friend = count

print(max_two_friend)
profile
Yunes
미래의 나를 만들어나가는 한 개발자의 블로그입니다.
이전 포스트

DFS & BFS

다음 포스트

우선순위 큐

0개의 댓글