[알고리즘/Swift] BOJ 4803 트리 :: 그래프, DFS + Python

이미지를 누르면 문제로 연결됩니다!

 

💡 풀이 방법

연결된 노드를 저장할 2차원 배열 graph, 방문처리를 위한 1차원 배열 visited 이 필요하다.

DFS 를 통해 트리가 아닌지를 확인하고 트리의 개수를 세는데, 노드 전체를 방문할 수 있도록 방문하지 않은 노드에 대해 DFS 를 수행한다. 

 

👀 DFS 과정에서 트리가 아닌지 확인하는 방법은 ?!

문제에서 주어진 "트리는 사이클이 없는 연결 요소이다." 를 통해,, 트리를 탐색하는데 사이클이 생긴다면, 트리가 아닌 것임을 체크한다. graph 배열에서는 연결된 노드를 전체 저장하므로, 이전에 방문한 노드를 사이클로 인식할 수 도 있다. 이를 방지하기 위해 다음 노드와 이전 노드가 같은지 확인하는 작업을 추가한다. (이전 노드 == 다음 노드) 는 이미 지나온 길이므로 DFS 를 수행하지 않고 무시한다.

 

👀 트리의 개수를 세는 방법 ?!

DFS 를 수행해서 방문처리를 했는데, 방문처리 배열 중 방문하지 않은 노드가 있다면 DFS 를 수행한다. 전체 노드를 방문하지 않고 DFS 가 종료되었다는 것은 특정 노드가 끊겨있다는 뜻이다. 재귀적으로 호출된 DFS 외에, 처음으로 호출되는 DFS 를 카운팅하면 트리의 개수를 셀 수 있다.

 

🤔 주의해야할 점

• 입력으로 들어오는 간선에 연결된 두 노드는 같을 수 있다. (같은 노드 연결 -> 트리가 맞음)
• 트리의 간선 개수가 0인 경우도 있다. (트리의 정점 6개, 간선 0개 -> 트리 6개)
• 출력 예시를 잘 맞추자 ... 

 

🐥 Swift 코드

func DFS(prev: Int, curr: Int, graph: [[Int]], visited: inout [Bool]) -> Bool {
    
    visited[curr] = true // 방문처리
    
    for next in graph[curr] {
        // 다음과 이전이 같은 경우, 같은 경로를 뜻하므로 무시
        if next == prev {
            continue
        }
        // next != prev, 이미 방문한 경우 사이클이 생기므로 트리가 아님
        if visited[next] {
            return false
        }
        // next != prev, 사이클이 없는 경우 DFS 수행
        // DFS 수행 도중 사이클이 생기면 false가 반환됨 -> 재귀적으로 false 반환
        if !DFS(prev: curr, curr: next, graph: graph, visited: &visited) {
            return false
        }
    }
    // DFS 수행 도중 사이클이 생기지 않으면 true 반환.
    return true
}

func BOJ_4803() {
    var i = 0
    while true {
        let line = readLine()!.split(separator: " ").map({Int($0)!})
        let n = line[0], m = line[1]
        if n == 0 && m == 0 { break }
        i += 1

        // 그래프와 방문처리 배열 초기화 및 데이터 입력 처리
        var graph: [[Int]] = Array(repeating: Array<Int>(), count: n+1)
        var visited: [Bool] = Array(repeating: false, count: n+1)
        for _ in 0..<m {
            let line = readLine()!.split(separator: " ").map({Int($0)!})
            graph[line[0]].append(line[1])
            graph[line[1]].append(line[0])
        }
        
        var tree = 0 // 트리의 개수
        for node in 1...n {
            if !visited[node] {
                // 해당 노드를 방문하지 않은 경우에만 DFS 수행
                if DFS(prev: 0, curr: node, graph: graph, visited: &visited) {
                    tree += 1 // 사이클이 생기지 않은 경우 트리의 개수 증가
                }
            }
        }
        if tree == 0 {
            print("Case \(i): No trees.")
        } else if tree == 1 {
            print("Case \(i): There is one tree.")
        } else{
            print("Case \(i): A forest of \(tree) trees.")
        }
    }
}

BOJ_4803()

 

🐍 Python3 코드

algorithmFor2021/dain_song