[Swift 알고리즘] 백준 11724 연결 요소의 개수

안녕하세요 코코종입니다. 오늘은 dfs에서 쉬운걸 들고왔습니다 ^^

처음에 조금 헷갈린 부분은 아무것도 연결되지 않은 정점에 대해서는 어떻게 해야하나..? 라는 생각을 했는데 예시나 자세한 설명이 없어서 조금 고민했습니다.(백준 진짜... 설명좀 자세히 해라) 일단 해당 정점도 요소라고 생각해서 했는데 맞았네요...?(조금 이상할지도)

예시로 n이 3, m이 1일 때 1 2 로만 입력이주어지면 1-2 3 이렇게 되어서 3은 카운트 하는건지 아닌지 몰라서 일단 세어줬는데 맞았네요....

3은 연결되지 않은 요소가 아닌가... 하는 생각이 들지만 맞았으니까 머 ㅎㅎ... 지나갑니다~

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/19.
//

import Foundation
// 백준 11724 연결 요소의 개수

// 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다
let input = readLine()!.split(separator: " ").map { Int(String($0)) ?? 0 }
let n = input.first!
let m = input.last!
var nodes: [[Int]] = Array(repeating: [], count: n+1) // key 에서 갈 수 있는 것들의 배열, 0번 인덱스 미사용
var isVisited = Array(repeating: false, count: n+1) // 0번 인덱스 미사용
var answer = 0

for _ in 0..<m {
    let line: [Int] = readLine()!.split(separator: " ").map { Int(String($0)) ?? 0 }
    let a: Int = line.first!
    let b: Int = line.last!
    nodes[a].append(b)
    nodes[b].append(a)
}

func dfs(a: Int) {
    isVisited[a] = true
    let stack = nodes[a] // a 입장에서 직접 연결된 애들
    for b in stack {
        if !isVisited[b] {
            dfs(a: b)
        }
    }
}

for i in 1...n {
    if !isVisited[i] {
        dfs(a: i)
        answer += 1
    }
}

print(answer)

처음에는 nodes를 딕셔너리로 하고 막 그랬는데 오히려 그 값을 받아서 또 append로 추가하고 다시 갱신해주는게 더 귀찮더라구요.... 어차피 인덱스에 바로 접근하기 때문에 O(1)이 나오는 것이라 큰 차이가 없어서 중간에 수정했습니다(코드가 더 길어져서 꼴뵈기 싫었음)

dfs하면 stack에 넣어서 뭐 맨 뒤에를 pop하고 하잖아요...? 근데 해보니까 막상 그럴 필요가 없더라구요! 그래서 stack이라고 이름 짓긴 했지만 stack처럼 안썼습니다! 단순히 for문 안에 넣어줘도 될 뻔 했네요!

맨 처음 방문한 정점을 방문처리 해주고 nodes[a]로 직접 연결된 애들을 하나씩 돌면서 그 정점이 방문하지 않은거면 방문 처리를 해주는 식으로 했습니다. 또한 마지막에 답을 구하기 위해 1~n까지의 정점을 돌면서 해당 정점이 방문처리 되어있지 않다면 dfs로 연결된 애들을 다~ 방문처리 하도록 했습니다!