구름톤 챌린지 Week 4 - Day 19

https://level.goorm.io/exam/195701/대체-경로/quiz/1

조금은 재미있는 문제다.

일반적인 BFS와 같되, 각 도시들을 하나씩 망가뜨려 갈 수 없는 상태로 만든다.

이런 모든 경우를 돌아보면서, 어떤 도시를 갈 수 없을 때, 최단 거리는 얼마인지 묻는 문제이다.

 

from collections import deque
from copy import deepcopy as dcopy
import sys
input = sys.stdin.readline


# do BFS
def BFS(start, end, graph):
    queue = deque([start])
    
    visited = [0] * (city + 1)
    visited[start] = 1
    
    while queue:
        now = queue.popleft()
        
        if now == end:
            return visited[end]

        for next in graph[now]:
            if visited[next] == 0:
                queue.append(next)
                visited[next] = visited[now] + 1
                
    return -1
    

city, road, start, end = map(int, input().split())
GRAPH = [[] for _ in range(city+1)]

# Adjacency List element add for bidirected
for _ in range(road):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    
# Adjacency List each element sort
for line in GRAPH:
    line.sort()

# Calculating shortest path that contain to pass cities
for i in range(1, city+1):
    if i == start or i == end:
        print(-1); continue
        
    graph = dcopy(GRAPH)    
    graph[i].clear()
    
    answer = BFS(start, end, graph)
    print(answer)

이번 문제도 사실상 다른 그래프 문제와 크게 다를 바가 없다.

하지만, 이동 경로를 판단하여 순차적으로 도시를 들려야 하기에 DFS보다는 BFS가 맞다.

 

from copy import deepcopy as dcopy

입력 코드, 인접 리스트로 선언하고 정렬하는 코드는 전부 생략한다.

기존에 풀었던 방법과 동일하여 굳이 설명할 필요가 없기 때문이다.

 

이 문제를 풀 때 핵심은 i번째는 건너뛰어야 한다.

for i in range(1, city+1)로 i를 받고, node == i라면 무시하는 방법을 사용해도 된다.

하지만 시간과 메모리 제한을 명시하지 않는 구름 사이트 특성상, 메모리 한계가 궁금해졌다.

그래서 굳이 copy 라이브러리를 사용하여 구현했다.

그럼에도 무난히 통과한 것을 보니 MLE보다는 TLE에 민감한 듯하다.

 

# Calculating shortest path that contain to pass cities
for i in range(1, city+1):
    if i == start or i == end:
        print(-1); continue
        
    graph = dcopy(GRAPH)    
    graph[i].clear()
    
    answer = BFS(start, end, graph)
    print(answer)

반복문을 돌면서 graph에 처음에 초기화한 GRAPH를 deepcopy한다.

그리고 i번째는 아예 지워버린다(clear()). 지운 graph를 기준으로 BFS를 돌면서 최단 거리를 찾는다.

 

# do BFS
def BFS(start, end, graph):
    while queue:
        now = queue.popleft()
        
        if now == end:
            return visited[end]
                
    return -1

일반적인 BFS와 다른 점은 위의 코드뿐이다.

BFS를 돌면서 now가 end 지점과 같다면, end의 visited 값을 반환한다.

이때 visited는 단순히 방문 여부만 있는 0과 1이 아니라, 몇 번째로 갔는지를 의미하는 int가 들어간다.

모든 부분을 탐색했음에도 if now == end로 함수를 빠져나가지 못하는 경우가 있다.

이 경우는 그래프에 end 지점이 없다는 말과 같다.

그런 경우 -1을 반환하여 갈 수 없음을 알려주어야 한다.