구름톤 챌린지 대체 경로 파이썬 195701
구름LEVEL
난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.
level.goorm.io
❏ 문제 설명
❍ 문제
플레이어는 1번부터 N번까지의 번호가 붙은 N개의 도시와 M개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.
플레이어는 차를 타고 S번 도시에서 E번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고,
플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은 출발 도시와 도착 도시를 포함해 네 개의 도시를 거치는 경로이므로, 플레이어는 해당 경로로는 이동하지 않을 것이다.
항상 가장 작은 수의 도시를 거치는 경로가 유일하지 않을 수 있다. 아래 그림과 같이 도시와 도로가 주어지고, 3번 도시에서 1번 도시로 이동하고자 할 때 가장 작은 수의 도시를 거치는 경로는 3 → 2 → 1과 3 → 4 → 1의 두 개가 있다. 이런 경우에 플레이어는 두 경로 중 아무 경로나 택해서 이동한다.
플레이어가 사는 나라에서는 자주 공사를 한다. i일 뒤에는 i번 도시에서 하루 동안 공사를 할 예정이다. 어떤 도시에서 공사를 하고 있으면, 그 도시에 연결된 모든 도로를 일시적으로 사용할 수 없다.
어떤 도시에서 공사를 하느냐에 따라 플레이어가 이동해야 하는 경로가 달라질 수 있다. 앞으로 N일 동안 매일 플레이어는 S번 도시에서E번 도시로 이동한다고 할 때, 각 날마다 플레이어가 이동하는 경로에 포함되는 도시의 수를 구해서 출력해보자. 단, 출발 도시와 도착 도시에서 공사를 하거나, 두 도시 사이를 이동할 수 없는 경우에는 -1을 대신 출력한다.
❍ 예제 설명
첫 번째 예제는 지문의 첫 번째 그림에 해당하는 예시이다.
1번 도시와 4번 도시가 공사 중일 때는 항상 두 도시 사이를 이동할 수 없다.
2번 도시와 5번 도시가 공사 중일 때는 1 → 3 → 4의 경로를 따라 이동할 수 있다. 경로에 포함된 도시는 세 개이다.3번 도시가 공사 중일 때는 1 → 3 → 4의 경로를 따라 이동할 수 없다. 따라서 1 → 5 → 2 → 4의 경로로 이동해야 하고, 이때 경로에 포함된 도시는 네 개이다.
두 번째 예제는 지문의 두 번째 그림에 해당하는 예시이다.
세 번째 예제에서 도시와 도로는 아래 그림과 같이 주어진다.
❍ 입력
첫째 줄에 도시의 수 N, 도로의 수 M, 그리고 출발 도시 S와 도착 도시 E가 공백을 두고 주어진다.
다음 M개의 줄에는 각 도로가 연결하는 두 도시의 번호 u, U가 공백을 두고 주어진다.
- $3 \leq N \leq 1000$
- $N - 1 \leq M \leq 2000$
- $1 \leq S, E \leq N; S \neq E$
- $1 \leq u,U \leq N; u \neq U$
- 어떤 도시에서도 공사를 하고 있지 않을 때, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.
- 입력에서 주어지는 모든 수는 정수이다.
❍ 출력
N개의 줄에 걸쳐 답을 출력한다. i번째 줄에는 i번 도시가 공사 중일 때 플레이어가 이동하는 경로에 포함되는 도시의 수를 출력한다. 만약 출발 도시 또는 도착 도시가 공사 중이거나, 두 도시 사이를 이동하는 것이 불가능한 경우에는 -1 을 대신 출력한다.
❏ 문제 풀이
해당 문제는 다익스트라로 풀이가 가능하다.
< 다익스트라 >
[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra
들어가며 본 포스팅에서는 다익스트라 최단 경로 알고리즘에 대해 소개합니다. 📌 다익스트라 최단 경로 알고리즘이란? 다익스트라 최단 경로 알고리즘이란, 가장 짧은 경로를 찾기 위한 알고
dmaolon00.tistory.com
시작 노드에서 모든 노드로까지의 최단 거리를 구할 수 있다.
❍ 변수 설명
import sys
import heapq
import copy
input = sys.stdin.readline
INF = int(1e9)
n, m, s, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, U = map(int, input().split())
graph[u].append(U)
graph[U].append(u)
for i in range(1, n + 1):
# 시작 노드나, 끝 노드가 공사 중인 경우
if s == i or e == i:
print(-1)
continue
distance = [INF] * (n + 1)
distance[s] = 1
dijkstra()
if distance[e] == INF:
print(-1)
else:
print(distance[e])- 노드의 최단 거리 초기화를 위해 INF를 지정하여 사용해주었다.
- graph로 간선을 양방향으로 연결해주었다.
- 1부터 n + 1까지의 for문을 통해, 공사 중이라 접근할 수 없는 노드를 표시할 수 있다.
- 최종적으로 도시의 개수를 출력하는 것이기에, 시작 노드의 최단 거리를 1로 초기화한다.
- 다익스트라를 통해 모든 노드까지의 최단 경로를 구하여 끝 노드의 거리를 출력한다.
❍ 다익스트라
def dijkstra():
q = []
heapq.heappush(q, (1, s)) # 시작 노드의 거리와, 시작 노드를 담아준다.
while q:
dist, now = heapq.heappop(q)
# 이미 현재 노드의 거리가 더 짧은 경로로 반영되어있다면, 건너뛰기
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 노드 탐색
for n in graph[now]:
# 해당 노드는 공사 중이 아니어야 한다.
if n != i:
cost = dist + 1
# 해당 노드의 기존 거리와, 현재 노드를 거쳐서 온 거리 비교
if cost < distance[n] :
distance[n] = cost
heapq.heappush(q,(cost, n))heap은 노드 중에 거리가 가장 짧은 노드를 pop으로 자동으로 꺼내올 수 있다. 따라서, (1, s)로 시작 노드의 거리와 시작 노드를 담아서 시작한다. 큐가 비워질 때까지 반복하며, 현재 노드와 거리를 꺼내온다.
먼저, 현재 가장 거리가 짧은 노드를 heap에서 꺼내온다. 그 후, 해당 노드의 기존 distance에 담겼던 거리가 이미 더 짧은 경로로 반영되어있다면, 그 후 과정은 건너뛴다.
현재 꺼내온 노드의 주변 노드를 탐색하며, 공사 중인 노드는 반영하지 않는다.
공사 중이지 않은 노드의 경우, 기존의 거리와 현재의 노드를 거치게 되는 거리를 비교한다.
만약, 현재의 노드를 거쳐 오는 것이 더 최단 거리인 경우, distance에 반영하고 힙에 담아준다.
❍ CODE_DIJKSTRA
import sys
import heapq
import copy
input = sys.stdin.readline
INF = int(1e9)
def dijkstra():
q = []
heapq.heappush(q, (1, s))
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for n in graph[now]:
if n != i:
cost = dist + 1
if cost < distance[n] :
distance[n] = cost
heapq.heappush(q,(cost, n))
n, m, s, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, U = map(int, input().split())
graph[u].append(U)
graph[U].append(u)
for i in range(1, n + 1):
if s == i or e == i:
print(-1)
continue
distance = [INF] * (n + 1)
distance[s] = 1
dijkstra()
if distance[e] == INF:
print(-1)
else:
print(distance[e])
그 다음은 구름톤에서 제공된 해설지에 따라 최단 거리에 자주 이용되는 알고리즘인 BFS를 이용하여 풀이를 진행해보았다.
❍ BFS
def bfs(s, i):
# 시작 노드가 공사중이라면
if s == i:
return -1
visited = [False] * (n + 1)
visited[s] = True
queue = deque([s])
count = 1
while queue:
count += 1
# 다음 레벨로 이동하지 않고, 바로 현재 레벨에서의 노드를 모두 처리한다.
for _ in range(len(queue)):
now = queue.popleft()
for x in graph[now]:
if x == i or visited[x]:
continue
if x == e:
return count
visited[x] = True
queue.append(x)
return -1공사 중인 노드이거나 방문 처리된 도시는 건너뛴다.
끝 도시를 만나게 되면, count를 리턴하고, 그렇지 않은 경우에는 방문 처리 후 큐에 담게 된다.
예를 들어 2번 도시가 공사중인 경우,
1 → 5 →
1 → 3 → 4
처럼 5의 경우 다음 경로가 없으므로 아무 것도 큐에 담지 못하고, 3의 경우에는 4로 이동할 수 있으며 끝 도시이기에 도시의 개수를 리턴하면 된다.
기존 BFS에서는 예제 1의 경우 1(s) → 5 → 2 → 4(e) → 3으로 탐색을 하게 된다.
위의 예시 처럼, 1 → (3, 5) → ( , 4)로 레벨별로 실행하고자 하려면 큐의 길이만큼 for문을 반복해주면 된다.
A
/ \
B C
| |
D E예를 들어 위와 같은 그래프가 있을 때, A → B → C → D → E로 BFS가 되는 것을, 큐의 길이대로 반복되는 for문을 추가함으로서, A → B, C → D, E가 된다.
즉, 레벨 1(B, C)와 레벨 2(D, E)가 있을 때, 현재의 레벨에 담긴 모든 노드를 처리할 수 있다는 것이다.
❍ CODE_BFS
import sys
from collections import deque
input = sys.stdin.readline
def bfs(s, i):
if s == i:
return -1
visited = [False] * (n + 1)
visited[s] = True
queue = deque([s])
count = 1
while queue:
count += 1
for _ in range(len(queue)):
now = queue.popleft()
for x in graph[now]:
if x == i or visited[x]:
continue
if x == e:
return count
visited[x] = True
queue.append(x)
return -1
n, m, s, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, U = map(int, input().split())
graph[u].append(U)
graph[U].append(u)
for i in range(1, n + 1):
print(bfs(s, i))❏ 삽질 기록
❍ Issue #1
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(s, i):
q = []
heapq.heappush(q, (1, s))
distance[s] = 1
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for n in graph[now]:
if i != n:
distance[n] = min(distance[n], distance[now] + 1)
heapq.heappush(q, (distance[now] + 1, n))
n, m, s, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, U = map(int, input().split())
graph[u].append(U)
graph[U].append(u)
for i in range(1, n + 1):
if s == i or e == i:
print(-1)
continue
distance = [INF] * (n + 1)
dijkstra(s, i)
if distance[e] == INF:
print(-1)
else:
print(distance[e])딱 하나의 케이스가 시간초과가 되었다. 어디를 만져주어야 할지 한참 헤매다가 태호 왕천재 덕에 해결을 했다.
distance[n] = min(distance[n], distance[now] + 1)
heapq.heappush(q, (distance[now] + 1, n))
노션에 다익스트라 알고리즘을 정리할 때, 내 마음대로 min을 통해 더 최단 거리를 distance에 반영해주고 heapq에 엉뚱하게 distance[now] + 1을 넣어주는 이상한 코드를 짜넣은 것이 문제였다.
따라서, 노션과 노션 기반으로 올렸던 티스토리 글, 깃헙에서의 코드도 모두 수정해주어, distance[now] +1이 기존의 distance[n]보다 작을 경우에만 힙에 추가해줄 수 있도록 하였다.