1967 swift - 트리의 지름

₩BFS 사용

[Swift] Breadth-First Search / BFS

1. 접근방법.

결국엔 Leaf 에서 Leaf의 길이를 재는 거니까, Leaf에서 갈 수 있는 모든 Leaf 들을 BFS로 탐색하여 가장 긴 것을 찾으면 된다고 판단. 

=> 시간 초과

var n = Int(readLine()!)!
var N = Array(repeating: 1, count: n)
var graph = Array(repeating: [(Int,Int)](), count: n+1)
var result = 0

func bfs(startLeaf: Int) -> Int{
	var visit = Array(repeating: false, count: n+1)
	visit[startLeaf] = true
	
	var queue = [(startLeaf, 0)]
	var idx = 0
	var maxDist = 0

	while queue.count > idx {
		let (curNode, curDist) = queue[idx]
		idx += 1
		
		if curDist >= maxDist {
			maxDist = curDist
		}
		
		for (nx, dist) in graph[curNode] {
			if !visit[nx] {
				visit[nx] = true
				queue.append((nx, curDist + dist))
			}
		}
	}
	return maxDist
}

while let input = readLine()?.split(whereSeparator: {$0==" "}).map({Int(String($0))!}) {
	let (parentNode, childNode, edgeCost) = (input[0], input[1], input[2])
	graph[parentNode].append((childNode, edgeCost))
	graph[childNode].append((parentNode, edgeCost))
	N[input[0]] = 0
}

for (index, value) in N.enumerated() {
	if value == 1 {
		result = max(bfs(startLeaf: index), result)
	}
}

print(result)

 

2. 다시 시도한 방법, 처음에 1번 노드로 부터 가장 큰 edge cost 를 가진 Leaf를 선정하여 해당 Leaf로 부터 다른 모든 Leaf를 찾아서 가장 max edge cost를 찾으면 된다.

var n = Int(readLine()!)!
var graph = Array(repeating: [(Int,Int)](), count: n+1)

func bfs(startNode: Int) -> (Int, Int){
	var visit = Array(repeating: false, count: n+1)
	visit[startNode] = true
	
	var queue = [(startNode, 0)]
	var idx = 0
	
	var maxDistance = 0
	var maxLeaf = 0

	while queue.count > idx {
		let (currentNode, currentDistance) = queue[idx]
		idx += 1
		
		if currentDistance >= maxDistance {
			maxDistance = currentDistance
			maxLeaf = currentNode
		}
		
		for (nx, dist) in graph[currentNode] {
			if !visit[nx] {
				visit[nx] = true
				queue.append((nx, currentDistance + dist))
			}
		}
	}
	
	return (maxDistance, maxLeaf)
}

for _ in 0..<n-1 {
	let input = readLine()!.split(whereSeparator: {$0==" "}).map({Int(String($0))!})
	let (parentNode, childNode, edgeCost) = (input[0], input[1], input[2])
	graph[parentNode].append((childNode, edgeCost))
	graph[childNode].append((parentNode, edgeCost))
}

let biggestLeaf = bfs(startNode: 1).1

print(bfs(startNode: biggestLeaf).0)

 

 

중간의 런타임 에러는 아래에서 난 것으로 추정 되어
[파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다.] 는 문제를 다시 읽고 해당 부분을 고쳐주어 통과하였다.

while let input = readLine()?.split(whereSeparator: {$0==" "}).map({Int(String($0))!})