[구름 LEVEL] 대체 경로 (Python)

[구름 LEVEL] 대체 경로

https://level.goorm.io/exam/195701/%EB%8C%80%EC%B2%B4-%EA%B2%BD%EB%A1%9C/quiz/1

문제 설명

· 공사 중인 도시를 거치지 않는 S 도시에서 E 도시까지의 최단 경로를 찾았을 때, 지나게 되는 도시의 수 구하기

접근 방법

· 일반적인 최단경로 찾기 문제와는 달리, 최단경로를 찾았을 때의 레벨(도시의 수) 도 계산해야 하므로 BFS에서 탐색하는 레벨로 도시를 나누기

· 한 레벨의 도시가 모두 탐색이 끝났다면, 하위 레벨의 도시 탐색하기

· 목표 도시를 찾았다면, 해당 도시가 위치한 레벨의 수 반환

· 공사중인 도시는 visited = True를 통해 탐색에서 제외

· 탐색이 끝난 후에도 목표 도시에 도달하지 못했다면 -1

알고리즘 설계 및 구현

from collections import deque

def get_route(n, start, end, city, ban):
    # 방문한 노드를 기록하는 리스트 초기화 (1부터 n까지 노드가 있다고 가정)
    visited = [False] * (n + 1)
    # 금지된 노드는 방문한 것으로 표시
    visited[ban] = True
    count = 0
    # BFS를 위한 큐 초기화
    queue = deque()
    # 다음 레벨의 노드를 담을 큐 초기화
    child = deque()
    # 시작 노드를 큐에 추가
    queue.append(start)

    while queue:
        # 다음 레벨의 노드를 담을 child 큐 초기화
        child = deque()
        # 이동 횟수 증가
        count += 1
        # 현재 레벨의 모든 노드를 처리
        for _ in range(len(queue)):
            current = queue.pop()
            # 현재 노드가 도착 노드이면 이동 횟수 반환
            if current == end:
                return count
            # 현재 노드를 방문하지 않았다면
            elif not visited[current]:
                # 현재 노드를 방문한 것으로 표시
                visited[current] = True
                # 현재 노드의 인접 노드를 모두 확인
                for neighbor in city[current]:
                    # 인접 노드를 방문하지 않았다면 child 큐에 추가
                    if not visited[neighbor]:
                        child.append(neighbor)
                        
        # 현재 레벨의 처리가 끝나면 child 큐를 queue로 설정
        queue = child
                
    # 도착 노드에 도달할 수 없는 경우 -1 반환
    return -1

n, m, s, e = map(int, input().split())
# 도시의 인접 리스트 초기화
city = [[] for _ in range(n + 1)]
# 방문 리스트 초기화
visited = [False] * (n + 1)

# 간선 정보 입력 받기
for _ in range(m):
    a, b = map(int, input().split())
    city[a].append(b)
    city[b].append(a)

# 각 노드를 금지된 노드로 설정하고 get_route 함수 호출
for i in range(n):
    print(get_route(n, s, e, city, i + 1))

결과