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

[문제 설명]

 출발지에서 목적지까지 최단거리로 이동하는 경우를 구하는 문제입니다.

 

[해결 방법]

해당 문제는 BFS를 사용해 풀이하는 문제입니다. BFS를 이용한 빠른 길 찾기는 출발점으로부터 인접 노드들의 최단거리를 갱신하는 구조입니다. 이 때, 출발점이 하나이고 목적지는 x개일 수 있습니다.

 

 주어진 예시를 보면 출발점은 x개인 반면에 도착점은 하나로 고정되어 있습니다. 즉, 도착점을 출발점으로 생각하여 인접 노드들의 최단거리 노드를 갱신하면 도착점에서부터 출발점까지의 최단거리를 구할 수 있습니다.

결과적으로 도착점을 출발점으로 탐색을 진행한다면 도착점에서 출발할 수 있는 모든 노드들의 최단거리를 구할 수 있습니다. sources 배열에 있는 노드들의 최단거리를 return하여 정답을 받을 수 있습니다.

 

각 노드들의 최단 거리

 

[해결 과정에서 발생한 문제와 해결방법] 

• 처음에는 다수의 출발점이기에 플로이드 와샬 알고리즘을 사용했지만 시간초과가 발생했습니다. 왜냐하면 플로이드 와샬의 시간복잡도는 O(n^3)인데 문제에서는 n이 10만이기 때문에 시간내에 통과할 수 없습니다.
• 초기 노드간의 연결을 표현하기 위해 N * N 배열을 사용했습니다. 이는 연결된 노드들의 거리를 갱신할 때 항상 N번을 반복해야해 제한시간 안에 문제를 해결할 수 없습니다.  (기존의 방법 코드 참조).
• 하지만 개선된 방법의 경우 최악의 경우에만 N번의 반복문을 수행하기에 더 효율적이고, 제한된 시간안에 문제를 해결할 수 있습니다.  

#기존의 방법
def find_next_node(start_point):
  for next in range(n):
     if map[start_point][next]:
     	calc_cost_to_next(start_point, next)
     

#개선된 방법
def find_next_node(start_point):
  for next in map[start_point]:
     calc_cost_to_next(start_point, next)

 

• 모든 노드들 사이의 거리가 1이기 때문에 BFS를 수행해야하는데 최단거리라는 키워드가 각인되어 데익스트라를 사용했습니다.

 

[정답 코드]

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

    answer = []

    war_map = [ [] for _ in range(n + 1)]

    for y, x in roads:
        war_map[y].append(x)
        war_map[x].append(y)

    cost_map_of_point = [987654321] * (n + 1)

    cost_arr = []
    cost_map_of_point[destination] = 0
    heapq.heappush(cost_arr, [0, destination])

    while cost_arr:
        cost, arrived_point = heapq.heappop(cost_arr)

        if cost_map_of_point[arrived_point] < cost:
            continue

        for next in war_map[arrived_point]:
            if cost + 1 < cost_map_of_point[next]:
                heapq.heappush(cost_arr, [cost + 1, next])
                cost_map_of_point[next] = cost + 1

    for source in sources:
        if cost_map_of_point[source] == 987654321:
            cost_map_of_point[source] = -1

        answer.append(cost_map_of_point[source])

    return answer



if __name__ == "__main__":
    print(solution(3, [[1, 2], [2, 3]], [2, 3], 1))