[구름톤 챌린지] 4주차 19일차 대체 경로

문제

---

플레이어는 $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 을 대신 출력한다.

입력

---

첫째 줄에 도시의 수 $N$, 도로의 수 $M$, 그리고 출발 도시 $S$와 도착 도시 $E$가 공백을 두고 주어진다.
다음 $M$개의 줄에는 각 도로가 연결하는 두 도시의 번호 $u, v$가 공백을 두고 주어진다.

 

 

• $3 \leq N \leq 1 \ 000$
• $N-1 \leq M \leq 2 \ 000$
• $1 \leq S, E \leq N; S \neq E$
• $1 \leq u, v \leq N; u \neq v$
• 어떤 도시에서도 공사를 하고 있지 않을 때, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.
• 입력에서 주어지는 모든 수는 정수이다.

출력

---

$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번 도시가 공사 중일 때 플레이어가 이동하는 경로에 포함되는 도시의 수를 출력한다. 만약 출발 도시 또는 도착 도시가 공사 중이거나, 두 도시 사이를 이동하는 것이 불가능한 경우에는 -1 을 대신 출력한다.

 

---

문제 접근 방식

---

매 쿼리마다 BFS를 취해주었다.

 

BFS가 되지 않는다면 -1을 반환하도록 했다.

 

---

정답 코드

---

# 대체 경로
import sys
input = sys.stdin.readline
from collections import deque

N, M, S, E = map(int, input().rstrip().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)

def BFS(IMP, S, E):
    visited = [0 for _ in range(N+1)]
    if IMP == S or IMP == E:
        return -1
    queue = deque()
    queue.append((S, 1))
    visited[S] = 1
    while queue:
        node, cnt = queue.popleft()
        if node == E:
            return cnt
        for near_node in graph[node]:
            if near_node != IMP and visited[near_node] == 0:
                visited[near_node] = 1
                queue.append((near_node, cnt+1))
    return -1

for i in range(1, N+1):
    print(BFS(i, S, E))

 

---

특별히 배운 점

---

이런 유형의 문제를 빠르게 구하는 방법이 있는 걸로 알고 있는데, 아직 배우지 않아서 배워봐야 겠다고 생각했다.