문제
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(100∗5100)=(510,000)
플로이드 워셜의 경우는?
O(100∗100∗100)=100,000)
여기서 플로이드 워셜의 경우 24번째줄 for문이 한 번 더 추가되니깐.. O(n3)+O(n) 정도가 될 것 같다.
물론 시간복잡도에서 낮은 차수에 대해서는 별로 신경을 쓰진 않지만.. ㅎ 굳이 따지자면..
그래서 백준에서 두 풀이방법으로 진행했을 때, BFS가 좀 더 빠른 것이지 않을까..?

후기
문제를 보자마자 BFS를 떠올렸는데, 이는 개인적으로 BFS를 플로이드-워셜보다 많이 풀어보고 익숙해서 그렇지 않았을까.. 라는 생각이 든다.
그리고 BFS, DFS의 시간복잡도는 언제나 헷갈려서 곰곰히 생각해야 떠올랐다..
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 14502 연구소(Swift) (1) | 2024.11.02 |
---|---|
[BOJ] 백준 28279 덱 2 (Swift) (0) | 2024.10.29 |
[BOJ] 백준 2745 진법 변환 (Swift) (1) | 2024.10.06 |
[BOJ] 백준 18110 solved.ac (Swift) (0) | 2024.02.19 |
[BOJ] 백준 10845 큐 (Swift) (0) | 2024.01.07 |