Processing math: 100%
본문 바로가기

PS/백준

[BOJ] 백준 1389 케빈 베이컨의 6단계 법칙 (Swift)

반응형

문제

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

풀이

이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.
BFS의 시간복잡도가 어떻게 될까도 생각해봤다.
O(V+E) 라는 점, 최악의 경우 O(100+5000) 이 될 것이라고 생각했다.

또한 모든 친구(N)에 대해 검사를 해봐야 하므로, O(V(V+E)) 이지 않을까..?
100×5100라면 충분히 통과할 것이라고 생각했다.

처음엔 다음과 같이 생각했다.
1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.
즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지 하고 생각하면서
bfs를 1번에서 특정 노드 까지의 비용을 모두 실행시켜야겠다고 생각했다.

문제를 천천히 다시 읽어보며 다시생각해봤다.
이 문제에는 "모든 사람은 친구 관계로 연결되어져 있다." 라는 조건이 있다.
이 말은 즉, 1번 노드에서 모든 노드로 도달이 가능하다는 점이다.
1번노드에 대해 BFS를 실행해 모든 depth를 더하면 그것이 케빈베이컨지수가 될 수 있다.

그래서 BFS를 실행하면서, Queue에서 노드를 꺼내고 다음 노드는 해당 노드의 depth+1로 설정하여 Queue에 담아주는 작업을 진행했다.
코드는 다음과 같으며 거의 BFS 기초와 동일하다.

let input = readLine()!.split { $0 == " " }.map { Int($0)! }
let n = input[0], m = input[1]
var graph = [[Int]](repeating: [], count: n + 1)
for _ in 0..<m {
let input = readLine()!.split { $0 == " " }.map { Int($0)! }
let a = input[0], b = input[1]
graph[a].append(b)
graph[b].append(a)
}
func bfs(start: Int) -> Int {
var visited = [Bool](repeating: false, count: n + 1)
visited[start] = true
var queue = [(start, 0)]
var index = 0
var result = 0
while queue.count > index {
let current = queue[index]
let node = current.0
let depth = current.1
result += depth
for nextNode in graph[node] {
if !visited[nextNode] {
visited[nextNode] = true
queue.append((nextNode, depth + 1))
}
}
index += 1
}
return result
}
var sum = Int.max
var result = -1
for i in 1...n {
let total = bfs(start: i)
if sum > total {
result = i
sum = total
}
}
print(result)

추가로 전날 플로이드-워셜 알고리즘을 통해 문제풀이한 것이 떠올라서 해당 알고리즘을 사용하여 풀이할 수 있지 않을까도 싶었다.
플로이드-워셜 알고리즘은 시간복잡도가 O(n3)이며 n이 100으로 아주 작은 수기 때문에 시간내에 풀 수 있다고 느꼈다.

let input = readLine()!.split { $0 == " " }.map { Int($0)! }
let n = input[0], m = input[1]
let INF = 1_234_567_789
var graph = [[Int]](repeating: [Int](repeating: INF, count: n), count: n)
for _ in 0..<m {
let input = readLine()!.split { $0 == " " }.map { Int($0)! - 1 }
let a = input[0], b = input[1]
graph[a][b] = 1
graph[b][a] = 1
}
for k in 0..<n {
for a in 0..<n {
for b in 0..<n {
if a == b { continue }
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
}
}
}
var result = 0
var total = Int.max
for i in 0..<n {
let sum = graph[i].reduce(0, +)
if total > sum {
result = i + 1
total = sum
}
}
print(result)

여기서 BFS로 푼 방식은 러프하게 계산해봤을 때 최악의 경우 연산이 다음과 같을 것이라고 생각했다.
O(1005100)=(510,000)

플로이드 워셜의 경우는?
O(100100100)=100,000)

여기서 플로이드 워셜의 경우 24번째줄 for문이 한 번 더 추가되니깐.. O(n3)+O(n) 정도가 될 것 같다.
물론 시간복잡도에서 낮은 차수에 대해서는 별로 신경을 쓰진 않지만.. ㅎ 굳이 따지자면..

그래서 백준에서 두 풀이방법으로 진행했을 때, BFS가 좀 더 빠른 것이지 않을까..?

후기

문제를 보자마자 BFS를 떠올렸는데, 이는 개인적으로 BFS를 플로이드-워셜보다 많이 풀어보고 익숙해서 그렇지 않았을까.. 라는 생각이 든다.
그리고 BFS, DFS의 시간복잡도는 언제나 헷갈려서 곰곰히 생각해야 떠올랐다..

반응형

'PS > 백준' 카테고리의 다른 글