[백준] (Swift) 11724번 - 연결 요소의 개수 (DFS 연습)

 

문제링크

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

문제 풀이

• 나는 아직 graph를 입력받는게 힘들다.
  • 이번에 사용한 방식은, 다음과 같다. graph라는 2차원 배열을 만들고, 그 안에 연결된 노드들로 채워주었다.

• 그리고 하나의 노드를 선택하고, 그 깊이를 전체 다 탐색한 한다음, 연결이 끊기면!! 새로운 그래프를 탐색해야하는 것이기 때문에 DFS 알고리즘을 사용했다.
• 마지막 main for문을 작성하는데 조금 힘들었다.
  
  • 방문하지 않은 노드인데 → 더 이상연결된 노드가 없다면 → 방문처리해주고, count를 증가시켜준다. (그래프하나가 더있다는 뜻이니까!)
  • 방문하지 않은 노드인데 → 다음 노드가 존재한다면 → dfs 재귀를 돌려서 탐색해준다.

 

전체 소스코드는 다음과 같다.

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/11724_%EC%97%B0%EA%B2%B0%20%EC%9A%94%EC%86%8C%EC%9D%98%20%EA%B0%9C%EC%88%98/main.swift

GitHub - deslog/Algorithm

// n : 노드(정점)의 개수
// m : 간선 개수 (연결요소)

var nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
var graph = Array(repeating: [], count: nm[0]+1)
var visited = Array(repeating: false, count: nm[0]+1)
var answer = 0
var depth = 0

for _ in 0..<nm[1] {
    let uv = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[uv[0]].append(uv[1])
    graph[uv[1]].append(uv[0])
}

func dfs(_ start: Int ,_ depth: Int) {
    visited[start] = true // 들어가자마자 방문처리 go
    for i in 0..<graph[start].count{ // 노드와 연결된 노드들 차례대로 방문
        let next = graph[start][i]
        if visited[next as! Int] == false{ // 만약 방문하지 않았던 노드면
            dfs(next as! Int, depth + 1) // 방문해서 다시 탐색
        }
    }
}

// main
for i in 1..<nm[0]+1 {
    if !visited[i] { //방문하지 않은 노드이고
        if graph[i].isEmpty { // 더이상 방문할 노드가 없다면 (그래프의 연결이 끊겼다면)
            answer += 1 // 새로운 그래프가 생성된것이기 때문에 answer += 1
            visited[i] = true // 그런 다음, 방문처리 go
        } else { // 연결된 그래프가 있다면
            dfs(i, 0) // dfs로 다음 다음 노드를 탐색하기 위해 dfs 재귀
            answer += 1 // 재귀가 끝나면 answer +=1
        }
    }
}

print(answer)