백준 1167 - Swift

 

 

백준 1167 - Swift

https://www.acmicpc.net/problem/1167

 

 

해당 문제는 일정의 공식?을 알고 있어야 쉽게 풀 수 있는 문제에요.

 

바로 

"임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당 하는 두 노드 중 하나다."

입니다.

 

즉, 그래프의 아무 노드에서 BFS를 돌렸을 때 나오는 노드가 트리의 지름에 해당하는 두 노드 중 하나이라는 말이에요.

그렇기 때문에 아무 노드로 BFS를 돌려서 구한 노드의 정렬의 max값으로

다시 BFS(max)를 돌리면 지름에 해당하는 두 노드 모두를 구할 수 있습니다.

 

그리고 해당 문제는 가중치를 계산해야 하기 때문에 저는 각 노드들이

해당 노드까지 가중치를 얼마나 쌓아왔는지를 포함하면서 구현하기 위해서 튜플을 사용했어요!

 

 

import Foundation

let v = Int(readLine()!)!

// (정점 번호, 가중치)의 튜플을 사용
var edgeArray: [[(Int, Int)]] = Array(repeating: [], count: v+1)
var visited = Array(repeating: false, count: v+1)
var distance = Array(repeating: 0, count: v+1)

// 첫번째 지름 노드
var firstMax = 1

func BFS(_ node: Int) {
    var queue = [Int]()
    queue.append(node)
    
    visited[node] = true
    
    while !queue.isEmpty {
        let currentNode = queue.removeFirst()
        
        for i in edgeArray[currentNode] {
            // i.0 = 정점 번호 (인접노드) / i.1 = 가중치
            if !visited[i.0] { // 방문한 적이 없다면,
                visited[i.0] = true
                queue.append(i.0)
                distance[i.0] = distance[currentNode] + i.1 // 이전 노드의 가중치 + 현재 노드의 가중치
            }
        }
    }
}

for _ in 1...v { // 정점의 개수만큼
    var currentNode = 0
    
    while true {
        let input = readLine()!.split(separator: " ").map { Int($0)! }
        
        currentNode = input[0] // 현재 정점 번호
        
        var i = 1
        while i < input.count - 1 {
            let edge = input[i]
            let value = input[i + 1]
            let temp = (edge, value)
            edgeArray[currentNode].append(temp)
            i += 2
        }
        
        if input.last == -1 { break }
    }
}

BFS(1)

print(distance)
// 첫 번째 최대 거리 노드 찾기
for i in 2...v {
    if distance[firstMax] < distance[i] {
        firstMax = i
    }
}

// 초기화
visited = Array(repeating: false, count: v+1)
distance = Array(repeating: 0, count: v+1)

BFS(firstMax)

// 최대 거리 출력
print(distance.max()!)