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

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

프로그래머스

 

2023.08.04 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

각 부대를 하나의 노드로 생각할 수 있습니다.

roads는 노드들의 연결 관계를 나타냅니다.

이 문제에서 설명 자체가 source에서 destination까지의 최단 거리를 구하는 것처럼 설명이 되어 있지만 거꾸로 생각하면 더 편했습니다.

 

destination으로부터 각 노드들까지의 거리를 구한다고 생각하면 됩니다.

destination을 출발지로 생각하자는 아이디어입니다!

즉, 출발지로부터 각 노드들까지의 최단 경로를 구하는 문제가 되었습니다.

 

roads 데이터를 딕셔너리에 저장합니다. 이것이 그래프를 구성합니다!

각 노드들끼리의 가중치가 1로 고정이기 때문에 여러 경로를 탐색할 필요 없이 BFS를 활용하여 출발지로부터 인접한 노드들을 한 Level씩 탐색하면 됩니다!

 

 

풀이

fileprivate func solution(_ n:Int, _ roads:[[Int]], _ sources:[Int], _ destination:Int) -> [Int] {
    var graph = [Int: [Int]]()
    
    for road in roads {
        graph[road[0], default: []].append(road[1])
        graph[road[1], default: []].append(road[0])
    }
    
    var distance = Array(repeating: -1, count: n+1) // i 번째 지역에서 destination 까지의 최단 거리, 이 값은 destination에서 i번째 지역까지의 최단 거리로 생각 가능
    distance[destination] = 0
    
    bfs(departure: destination, graph: graph, distance: &distance)
    
    return sources.map { distance[$0] }
}

fileprivate func bfs(departure: Int, graph: [Int: [Int]], distance: inout [Int]) {
    var queue = [Int]()
    queue.append(departure)
    
    while !queue.isEmpty {
        let cur = queue.removeFirst()
        let nextNodes = graph[cur, default: []]
        
        for node in nextNodes {
            if distance[node] != -1 { continue }
            distance[node] = distance[cur] + 1
            queue.append(node)
        }
    }
}

distance 배열을 생성하여 출발지(여기서는 destination)로부터 i번째 노드까지의 거리를 기록합니다.

탐색을 시작하기전에 distance[destination] = 0 을 해줘야 합니다! (출발지에서 출발지까지의 거리는 당연히 0이기 때문)

 

bfs 함수는 일반적인 구성입니다.

큐에 노드를 넣고 하나씩 빼면서 인접한 노드를 찾습니다.

노드를 중복 방문하는 것을 막기 위해 distance[node]가 -1이 아닌 경우는 이미 방문한 노드이기 때문에 continue 시켰습니다.

distance 배열에 1씩 증가한 값을 넣습니다.

큐에 인접한 노드를 하나씩 넣고 이 과정을 반복합니다.

 

이 과정을 모두 마치면 distance 배열에는 i번째 노드로부터 destination 까지의 최소 거리가 들어있습니다.

우리가 리턴해야하는 값은 source로부터 destination까지의 거리이기 때문에

sources.map { distance[$0] } 을 리턴하면 됩니다!

 

 

마무리

source로부터 destination까지의 거리가 아닌 destination으로부터 source까지의 거리로 생각하는 것이 주요했습니다.

이렇게 하면 한번의 BFS로 destination으로 부터 모든 노드까지의 최단 거리를 구할 수 있기 때문입니다.

각 source마다 탐색을 해서 destination 까지의 거리를 각각 구하면 비효율적입니다.

 

이후에는 가중치가 모두 1이기 때문에 일반적인 그래프 탐색 코드를 작성하면 됐습니다.

만약 가중치가 1이 아니었다면 다이크스트라를 사용했을 것 같습니다!