[프로그래머스 lv3] 부대복귀

🔗 출처

https://school.programmers.co.kr/learn/courses/30/lessons/132266

✅ 아이디어

1. 그래프 탐색 - BFS
2. memorization

❌ 오답

from collections import deque

def makeGraph(n, roads):
    graph = {}
    for i in range(1, n+1):
        graph[i] = []
    
    for i in roads:
        if i[0] not in graph:
            graph[i[0]] = [i[1]]
        else:
            graph[i[0]].append(i[1])
        
        if i[1] not in graph:
            graph[i[1]] = [i[0]]
        else:
            graph[i[1]].append(i[0])
    return graph

def solution(n, roads, sources, destination):
    answer = []
    graph = {}
    result = []
    graph = makeGraph(n, roads)
    
    def bfs(src, dest):
        visited = {}
        queue = deque()
        queue.append((src, 0))
        while queue:
            v, distance = queue.popleft()
            for i in graph[v]:    
                if i not in visited:
                    if i == destination:
                        return distance + 1
                    queue.append((i, distance + 1))
                    visited[i] = distance + 1
        return -1


    
    for i in sources:
        if i == destination:
            result.append(0)
        else:
            a = bfs(i, destination)
            result.append(a)
        
    return result

정답풀이

from collections import deque

def solution(n, roads, sources, destination):
    answer = []
    graph = [[] for _ in range(n+1)]
    costs = [-1 for _ in range(n+1)]
    costs[destination] = 0
    queue = deque([destination])
    for n1, n2 in roads:
        graph[n1].append(n2)
        graph[n2].append(n1)
    while queue:
        x = queue.popleft()
        for node in graph[x]:
            if costs[node] == -1:
                queue.append(node)
                costs[node] = costs[x] + 1
    for s in sources:
        answer.append(costs[s])
    return answer
    

(참고) https://moneygear.tistory.com/26

🔥 배운것

1. 시간복잡도를 줄이기 위해 BFS 에서도 dp 의 memorization 처럼 결과를 미리 저장하여 사용할 수 있다.
2. visited 에 매몰되지 말 것 ( cost 도 있다 )