문제 정보


image

풀이

해당 문제는 그래프에서 쌍방향으로 연결되어 있는 노드의 개수를 카운트하는 것으로 이해하였다
나는 이 문제를 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)