[프로그래머스] 부대복귀 (파이썬)

문제

코딩테스트 연습 - 부대복귀

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

제한사항

🧭 접근

탐색류 문제이므로 BFS를 사용하면 되겠다고 생각했는데,
일부 케이스에서 시간 초과가 발생했다. 시간복잡도를 줄이기위해 다각도로 접근해 보았는데, 도착지가 모두 같으므로 도착지를 출발지로 정해 한번의 탐색을 통해 모든 경로에 대한 소요 시간을 탐색하였다.

✔ 풀이

1. 양방향 탐색을 위한 그래프 만들기
2. BFS를 이용하여 탐색 및 방문 노드까지의 소요시간 추가
3. BFS를 이용하여 시작 -> 레버, 레버 -> 출구 까지의 거리 구하기

📙 소스 코드

from collections import deque

def bfs(graph, st):
    q = deque()
    visited = [0] * (ncnt+1)
    time = [0] * (ncnt+1)
    q.append(st)
    visited[st] = 1
    cnt = 0
    while q:
        nd = q.popleft()
        if nd in graph:
            for n in graph[nd]:
                if visited[n] == 0:
                    q.append(n)
                    visited[n] = 1
                    time[n] = time[nd] + 1
    
    return time

def solution(n, roads, sources, destination):

    global ncnt; ncnt = n # 전역변수 선언
    graph = {} # 양방향 그래프 추가
    for x,y in roads:
        if x in graph:
            graph[x].append(y)
        else:
            graph[x] = [y]
        if y in graph:
            graph[y].append(x)
        else:
            graph[y] = [x]
	# 도착점 부터 모든 경로에 대한 소요시간 배열
    time_arr = bfs(graph,destination) 
   

    res = []
    for s in sources:
        ti = time_arr[s] # 부대원 위치까지 걸린 시간
        # 출발, 도착지가 다른데 0인경우 방문 불가한곳
        if s != destination and ti == 0: 
            res.append(-1)
        else:
            res.append(ti)
    
    return res

🤔 느낀 점

시간복잡도가 초과될 시, 단순 코드 연산을 줄이는 것이 아니라 알고리즘을 다시 검토하는 것이 좋을 것 같다.
발상의 전환의 중요성 !