[알고리즘/Swift] 2606 바이러스
문제 정보
풀이
해당 문제는 그래프에서 쌍방향으로 연결되어 있는 노드의 개수를 카운트하는 것으로 이해하였다
나는 이 문제를 BFS(Breadth-First-Search)를 이용하여 풀이하였다
DFS로도 풀 수 있는 문제였지만 점진적으로 퍼져가는 바이러스를 시각적으로 표현하기에는 BFS가 적당할 것 같았다
for i in 0..<M {
let a = readLine()!.split(separator: " ").map{Int(String($0))!}
lst[a[0]].append(a[1])
}
visited[1] = true
while !queue.isEmpty {
let target = queue.removeFirst()
for node in lst[target] {
if !visited[node] {
queue.append(node)
visited[node] = true
count += 1
}
}
}
처음 틀린 풀이에서는 쌍방향이라는 것을 고려하지 못하고 1 2
가 들어오면 배열 index 1에 2를 넣어주는 방식으로 접근하여
queue에서 하나씩 꺼내 아직 방문하지 않은 해당 index에 있는 배열의 원소값을 queue에 다시 넣는 방식으로 진행하였다
이런 식으로 풀이를 할 경우 주어진 입력 데이터에서 정상적으로 작동하지만 단방향으로만 그래프 탐색이 작동하여 다음과 같은 반례가 존재하였다
6
5
6 5
5 4
4 3
3 2
2 1
-> count = 0
분명히 컴퓨터들은 쌍방향 연결이지만, 내가 직전에 짠 코드는 앞에 써져 있는 숫자의 컴퓨터가 뒤에 써져 있는 숫자의 컴퓨터로 바이러스가 퍼지는 경우만 고려하였다
그러므로 다음과 같이 코드를 변경해주었다
단순히 반대방향으로의 경우도 배열에 넣어줌으로 해결될 수 있었던 이유는 vistied배열이 작동하기 때문이다
for i in 0..<M {
let a = readLine()!.split(separator: " ").map{Int(String($0))!}
//양방향 그래프 처리
lst[a[0]].append(a[1])
lst[a[1]].append(a[0])
}
이번 문제를 통해서 단방향, 쌍방향 그래프의 구분을 할 수 있게 되었고
BFS 문제를 항상 풀던 방식이 아닌 다른 방식으로 풀 수 있었다
전체 코드
import Foundation
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var lst: [[Int]] = Array(repeating: [], count: N+1)
var visited: [Bool] = Array(repeating: false, count: N+1)
//1번 컴퓨터부터 바이러스가 퍼지기 시작함
var queue: [Int] = [1]
var count = 0
for i in 0..<M {
let a = readLine()!.split(separator: " ").map{Int(String($0))!}
//양방향 그래프 처리
lst[a[0]].append(a[1])
lst[a[1]].append(a[0])
}
visited[1] = true
while !queue.isEmpty {
let target = queue.removeFirst()
//queue에서 꺼낸 컴퓨터와 연결된 컴퓨터 찾음
for com in lst[target] {
//아직 방문하지 않은 노드일경우
if !visited[com] {
queue.append(com)
visited[com] = true
count += 1
}
}
}
print(count)