2606번: 바이러스

문제 풀이 아이디어

연결된 node를 방문하며 세는 전형적인 dfs 문제입니다. 연결된 컴퓨터들을 인접리스트에 저장하고 1번 컴퓨터에서 시작하는 dfs를 실행합니다.

코드

전역에 cnt를 두고 갯수를 세기

// 입력 받기
let N = Int(readLine()!)!
let V = Int(readLine()!)!

// 인접 리스트에 간선 저장
var adj = Array(repeating: [Int](), count: N + 1)
for _ in 0..<V {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    adj[input[0]].append(input[1])
    adj[input[1]].append(input[0])
}

// 방문 체크용 배열
var visited = Array(repeating: false, count: N + 1)
visited[1] = true //👉 1번은 방문처리 (이미 감염)

// 감염된 컴퓨터의 수를 세는 변수
var cnt = 0

// dfs 구현
func dfs(now: Int) {
    for i in adj[now] {
        if !visited[i] {
            visited[i] = true
            cnt += 1 //👉 새로운 node방문할 때마다 cnt + 1
            dfs(now: i)
        }
    }
}

dfs(now: 1)
print(cnt)

dfs 내부에 cnt를 두고 갯수를 세기

// 입력 받기
let N = Int(readLine()!)!
let V = Int(readLine()!)!

// 인접 리스트에 간선 저장
var adj = Array(repeating: [Int](), count: N + 1)
for _ in 0..<V {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    adj[input[0]].append(input[1])
    adj[input[1]].append(input[0])
}

// 방문 체크용 배열
var visited = Array(repeating: false, count: N + 1)
visited[1] = true //👉 1번은 방문처리 (이미 감염)

// dfs 구현: 1번 컴퓨터와 연결된 컴퓨터를 센다
func dfs(now: Int) -> Int {
    // 현재 dfs를 돌고 있는 컴퓨터 1대
    var cnt = 1
    
    for i in adj[now] {
        if !visited[i] {
            visited[i] = true
            cnt += dfs(now: i) //👉 현재 dfs를 돌고 있는 컴퓨터에 연결된 컴퓨터 추가
        }
    }
    
    return cnt
}

// 1번 컴퓨터 때문에 감염되는 컴퓨터의 숫자를 구해야 하므로 1번 컴퓨터 1개는 제외하고 출력한다.
print(dfs(now: 1) - 1)