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

문제

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

실패 코드

from collections import deque

def bfs(roads, source, destination):
    queue = deque()
    queue.append((source, 0))
    
    while queue:
        road, cnt = queue.popleft()
        if road == destination:
            return cnt
        
        for i in roads:
            if i[0] == road:
                queue.append((i[1], cnt+1))
            elif i[1] == road:
                queue.append((i[0], cnt+1))
    return -1
    
    

def solution(n, roads, sources, destination):
    answer = []

    for source in sources:
        answer.append(bfs(roads, source, destination))
        
    return answer

• 시간초과,,,,,,,,
• 각 source➡️destination의 거리를 각각 구하려고 해서 시간초과가 발생한 것 같다.

정답 코드

from collections import deque

def solution(n, roads, sources, destination):
    answer = []
    graph = dict() # 각 노드에서 갈 수 있는 이웃 노드를 나타냄
    
    for a, b in roads:
        if a not in graph:
            graph[a] = [b]
        else:
            graph[a].append(b)
        
        if b not in graph:
            graph[b] = [a]
        else:
            graph[b].append(a)
            
            
    visited = [False for i in range(n+1)] # 노드 방문 했는지
    distance = [-1 for i in range(n+1)] # detination에서 각 source까지의 거리
    
    queue = deque()
    queue.append((destination, 0)) # destination부터 시작!!!
    
    while queue:
        node, cnt = queue.popleft()
        
        if visited[node]:
            continue
        
        visited[node] = True
        distance[node] = cnt
        
        for i in graph[node]:
            queue.append((i, cnt+1))
            
    
    for i in sources:
        answer.append(distance[i])
    
    
    return answer

• source➡️destination이 아니라 destination➡️source까지의 거리를 구하면서 한 번의 BFS로 시간초과 해결

한 발자국 다가가면 열 발자국 멀어지는 그래프 문제 ^_ㅠ