[알고리즘] 부대복귀 프로그래머스 Lv3. 파이썬

코드: Algorithm_test/Python3/프로그래머스/3/132266. 부대복귀/부대복귀.py at main · ddalkyTokky/Algorithm_test · GitHub

 

1. BFS

문제만 봐서는 정말 간단한 BFS, DFS 문제이다.

 

2. 역순 BFS

그런데 이제 역순이었다.. Source를 순회하면서 Source => Destination 의 경로를 찾으려면 For Loop 을 N만큼 순회해야한다는 얘기가 된다. 이를 막기 위해, 아래 3가지를 수정했다.

1. destination에서 출발해서 거리를 측정할것.
2. visited를 list가 아닌 dictionary로 선언
3. visited의 key는 각 노드, value는 destination까지의 거리

 

3. 최종 코드

def solution(n, roads, sources, destination):
    answer = []
    dict_road = {}
    for r in roads:
        if(r[0] in dict_road):
            dict_road[r[0]].append(r[1])
        else:
            dict_road[r[0]] = [r[1]]
            
        if(r[1] in dict_road):
            dict_road[r[1]].append(r[0])
        else:
            dict_road[r[1]] = [r[0]]
            
    queue = [destination]
    visited = {}
    visited[destination] = 0
    while(len(queue) != 0):
        current = queue.pop(0)
        if(current not in dict_road):
            continue
        for item in dict_road[current]:
            if(item not in visited):
                queue.append(item)
                visited[item] = (visited[current] + 1)      
    for s in sources:
        if(s in visited):
            answer.append(visited[s])
        else:
            answer.append(-1)
    return answer

4. 시간 복잡도

행위	시간 복잡도
sources 의 길이	N
roads 의 길이	M
roads를 딕셔너리로 재포장하기	O(M)
역순 BFS	O(M + V)
answer에 결과 담기	O(N)
최종	O(N) + O(M + V)