[Swift][프로그래머스][그래프] 가장 먼 노드

요구능력

넓이우선탐색(BFS) + 그래프

 

문제풀이

항상 그래프문제에서는 간선이 주어지면 인접리스트를 만들어야된다.

나는 graph 프로퍼티에 2차원배열로 인접리스트를 만들었다.

 

이렇게 만들면 graph[1] = [2, 3]과 같이 1번노드는 2번과 3번과 연결되어있다고 저장할 수 있다.

여기서 1번노드를 타고 2번노드를 들어가면 그대로 1번이 또 있게된다.

이 부분은 visited로 방문처리를 함으로써 재방문하지 않게해줄것이다.

 

문제에서 최단경로로 이동해야된다고 했다.

최단경로하면 가장 먼저 생각나는 알고리즘은 BFS이다.

BFS를 사용해서 노드를 탐색하는데, 1번노드에서 가장 먼 노드의 개수를 찾아야되므로, maxCount변수에 가장 먼 거리를 저장해줬다.

moveCntArr에는 거리에있는 노드를 구해서 넣어줬다.

예를들어서 2번과 3번노드는 1번으로부터 거리가 1이니까 moveCntArr[1] = [2, 3]이 된다.

 

BFS탐색이 모두 끝나고, moveCntArr[maxCount]를 하면 가장먼 거리의 노드들이 나오게된다.

개수를 리턴해줘야하므로 moveCntArr[maxCount].count를 리턴해준다.

 

후기

BFS와 그래프의 원리만 안다면 금방 풀고 넘어갈만한 문제같다.

 

코드

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph = Array(repeating: [Int](), count: n + 1)
    for i in edge{
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    }
    var maxCount = 0
    var moveCntArr = Array(repeating: [Int](), count: 50001)
    func bfs(){
        var queue = [(Int, Int)]() //노드번호, 이동횟수
        var visited = Array(repeating: false, count: n + 1)
        queue.append((1, 0))
        visited[1] = true
        while !queue.isEmpty{
            let (node, moveCnt) = queue.removeFirst()
            moveCntArr[moveCnt].append(node)
            maxCount = max(moveCnt, maxCount)
            for i in graph[node]{
                if !visited[i]{
                    queue.append((i, moveCnt + 1))
                    
                    visited[i] = true
                }
            }
        }
    }
    bfs()
    
    return moveCntArr[maxCount].count
}