[코딩테스트] 최단 경로

JY·2022년 7월 9일
코딩테스트
0

최단 경로

: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

  • 보통 그래프를 이용해 표현, 각 지점은 '노드', 지점간 연결된 도로는 '간선'
  • 코딩테스트에서 주로 단순히 최단 거리를 출력하도록 요구
  • 그리디 알고리즘, 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용되는 특징

다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

: 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

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

특징

  • 음의 간선을 표현되지 않으므로 GPS 소프트웨어의 기본 알고리즘으로 채택
  • 기본적으로 그리디 알고리즘으로 분류
    => 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정 반복
  • 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트(=최단 거리 테이블)에 저장하며 리스트 갱신
  • 매번 현재 처리하고 있는 노드를 기준으로 주변 간선 확인
  • 방문하지 않은 노드 중 현재 최단 거리가 가장 짧은 노드 확인
  • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾음

간단한 다익스트라 알고리즘

  • 시간 복잡도: O(V2)O(V^2) (VV: 노드 개수)
    -> 총 O(V)O(V)번에 걸쳐서 최단 거리 가장 짧은 노드 매번 선형 탐색,
         현재 노드와 연결된 노드 매번 일일이 확인
  • 처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언
    그 후 단계마다 '방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = int(input())  # 시작 노드 번호 입력 받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
visited = [False] * (n+1)  # 방문한 적이 있는지 체크하는 목적의 리스트 만들기
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a,b,c = map(int, input().split())
    graph[a].append((b,c))  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0  # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start] = 0  # 시작 노드에 대해서 초기화
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    for i in range(n-1):  # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:  # 현재 노드와 연결된 다른 노드를 확인
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:  
                distance[j[0]] = cost

dijkstra(start)  # 다익스트라 알고리즘 수행

for i in range(1, n+1):  # 모든 노드로 가기 위한 최단 거리 출력
    if distance[i] == INF:  # 도달할 수 없는 경우
        print("INFINITY")  # 무한이라고 출력
    else:  # 도달할 수 있는 경우
        print(distance[i])  # 거리 출력
입력되는 데이터 수가 많다는 가정하에 파이썬 내장 함수인 input()을 더 빠르게 동작하는 
sys.std.realine()으로 치환하여 사용
모든 리스트는 (노드의 개수+1)의 크기로 할당
노드의 번호를 인덱스로 하여 바로 리스트 접근 가능

입력 

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

출력 

0
2
3
1
2
4

개선된 다익스트라 알고리즘

  • 노드의 개수 및 간선의 개수가 많을 때 사용
  • 시간 복잡도: O(ElogV)O(ElogV) (VV: 노드 개수, EE: 간선 개수)
  • 힙 자료구조 사용
    -> 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리
    => 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빨리 찾기 가능
  • 현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐 추가 이용
    -> 거리 짧은 노드 선택할 때 우선순위 큐에서 그냥 노드를 꺼내면 된다.
    -> 우선순위 큐에서 노드 꺼낸 뒤 해당 노드를 이미 처리한 적 있다면 무시,
         아직 처리하지 않은 노드에 대해서만 처리.
  • '최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체

힙 자료구조

  • 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용
    -> 우선순위 큐: 우선순위가 가장 높은 데이터를 가장 먼저 삭제
  • PriorityQueue 또는 heapq 사용
  • 우선순위 큐 라이브러리에 데이터 묶음 넣으면 첫 번째 원소를 기준으로 우선순위 설정
  • 최소 힙 이용: 값이 낮은 데이터가 먼저 삭제
    최대 힙 이용: 값이 큰 데이터가 먼저 삭제
    -> 파이썬 라이브러리에서는 기본적으로 최소 힙 구조 이용
    (최소 힙을 최대 힙처럼 사용하기 위해 우선순위에 해당하는 값에 (-) 부호를 붙여 넣었다가 우선순위 큐에서 꺼낸 다음에 다시 (-) 부호 붙여 원래 값으로
  • 우선순위 큐에서 데이터 개수가 NN개일 때 힙 자료구조를 이용하면 전체 시간 복잡도: O(NlogN)O(NlogN)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = int(input())  # 시작 노드 번호 입력 받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a,b,c = map(int, input().split())
    graph[a].append((b,c))  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    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]))

dijkstra(start)  # 다익스트라 알고리즘 수행

for i in range(1, n+1):  # 모든 노드로 가기 위한 최단 거리 출력
    if distance[i] == INF:  # 도달할 수 없는 경우
        print("INFINITY")  # 무한이라고 출력
    else:  # 도달할 수 있는 경우
        print(distance[i])  # 거리 출력

=> 한 번 처리된 노드는 처리되지 않음

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

: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용되는 알고리즘

  • 단계마다 거쳐 가는 노드를 기준으로 알고리즘 수행
  • 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요 없음
  • 시간 복잡도: O(N3)O(N^3)
  • 다이나믹 프로그래밍
    -> 노드의 개수가 N개일 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신
  • 점화식:   Dab=min(Dab,  Dak+Dkb)D_{ab} = min(D_{ab},~~ D_{ak}+D_{kb})
    => '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 = map(int, input().split())
    graph[a][b] = c  # 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):
        if graph[a][b] == INF:  # 도달할 수 없는 경우
            print("INFINITY", end=" ")
        else:  # 도달할 수 있는 경우
            print(graph[a][b], end=" ")  # 거리 출력
    print()

입력

4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

출력

0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0

실전문제

Ex1) 미래도시

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해있으며, X번 방문해 물건을 판매하고자 한다.
공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다.
또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문 판매원 A는 1번 회사에 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표이다. 이 때 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다. 방문 판매원이 회사 사이를 이동하게 되는 최서 시간을 계산하는 프로그램을 작성하시오. 이때 소개팅의 상대방과 커피를 마시는 시간을 고려하지 않는다고 가정한다. 예를 들어 N=5, X=4, K=5이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.

(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), 
(3번, 5번), (4번, 5번)

이 때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1번-3번-5번-4번)으로 설정하면, 소개팅에 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있다. 따라서 이 경우 최소 이동시간은 3이다.

입력조건
- 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1 ≤\leq N,M ≤\leq 100)
- 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
- M+2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1 ≤\leq K ≤\leq 100)

출력조건
- 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
- 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

sol) 플로이드-워셜 알고리즘 사용 (N 범위가 한정적이므로 이를 사용하는 것이 유리)
1번 노드에서 X를 거쳐 K로 가는 최단 거리
= (1번 노드에서 X까지 최단거리) + (X에서 K까지의 최단 거리)

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split())  # 노드 수, 간선 수 입력 받기
# 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 = map(int, input().split())
    # A와 B가 서로에게 가는 비용은 1이라 설정
    graph[a][b] = 1
    graph[b][a] = 1
    
# 거쳐갈 노드 X, 최종 목적지 노드 K 입력 받기
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘 수행
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])

# 수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

if distance >= INF:  # 도달할 수 없는 경우
    print("-1")
else:  # 도달할 수 있는 경우
    print(distance)  # 거리 출력

Ex2) 전보

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메세지를 보낼 때는 일정 시간이 소요된다.
어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다. (1 ≤\leq N ≤\leq 30,000, 1 ≤\leq M ≤\leq 200,000, 1 ≤\leq C ≤\leq N)
- 둘째 줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메세지가 전달되는 시간이 Z라는 의미다.

출력조건
- 첫째 줄에 도시 C에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

sol) 다익스트라 알고리즘 사용 (한 도시에서 다른 도시까지의 최단 거리로 치환 가능)
N,M의 범위가 충분히 크므로 우선순위 큐를 이용하여 다익스트라 알고리즘 작성

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m, start = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    x,y,z = map(int, input().split())
    graph[x].append((y,z))  # z번 노드에서 y번 노드로 가는 비용이 z라는 의미

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    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]))

dijkstra(start)  # 다익스트라 알고리즘 수행

count = 0  # 도달할 수 있는 노드 개수
max_distance = 0  #도달할 수 있는 노드 중, 가장 멀리 있는 노드와의 최단 거리
for d in distance:
    if d != INF:  # 도달할 수 있는 경우
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야하므로 count-1 출력
print(count-1, max_distance)

기출문제

Q40 숨바꼭질

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1~N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 헛간으로 도달이 가능한 형태로 주어집니다.
동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에는 N과 M이 공백으로 구분하여 주어집니다. (2 ≤\leq N ≤\leq 20,000), (1 ≤\leq M ≤\leq 50,000)
- 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 ≤\leq A,B ≤\leq N)

출력조건
- 첫째 줄에는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호를 출력합니다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

sol) 다익스트라 알고리즘을 이용하여 1번 헛간으로부터 다른 모든 노드로의 최단 거리를 계산한 뒤 가장 최단 거리가 긴 노드를 찾는다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = 1  # 시작 노드를 1번 헛간으로 설정
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a, b = map(int, input().split())
    # a번 노드와 b번 노드의 이동 비용이 1 (양방향)
    graph[a].append((b,1))
    graph[b].append((a, 1))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    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]))

dijkstra(start)  # 다익스트라 알고리즘 수행

max_node = 0  # 최단 거리가 가장 먼 노드 번호 (동빈이가 숨을 헛간의 번호)
max_distance = 0  #도달할 수 있는 노드 중, 최단 거리가 가장 먼 노드와의 최단 거리
result = []  # 최단 거리가 가장 먼 노드와의 최단 거리와 동일한 최단 거리를 가지는 노드들의 리스트

for i in range(1, n+1):
    if max_distance < distance[i]:
        max_node = i
        max_distance = distance[i]
        result = [max_node]
    elif max_distance == distance[i]:
        result.append(i)

print(max_node, max_distance, len(result))

입력 

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

출력 

4 2 3

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)
profile
JY
이전 포스트

[백준 파이썬] 16401번 과자 나눠주기

다음 포스트

[백준 파이썬] 17182번 우주 탐사선

0개의 댓글