백준 1068번 트리 - SWIFT

문제

---

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

 

 

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

 

 

이제 리프 노드의 개수는 1개이다.

 

 

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

 

 

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

 

문제 링크

1068번: 트리

 

 

풀이

---

평범한 트리 문제다.

문제에서는 입력으로 부모 노드 정보를 줬다.

이 정보를 뒤집으면 특정 노드의 자식 노드 정보가 된다.

트리를 순회할 때 특정 순회 방식으로 하라는 명령이 없었으므로 위에서부터 차례대로 dfs를 사용해서 순회할 것이다.

dfs로 순회를 하면 트리의 하위 레벨로 내려가기만하지 올라오는 순회는 없다.

그래서 트리 방금 입력 정보를 뒤집어서 구한 자식 정보만 입력해도 순회하는데는 문제가 없다.

처음에는 노드 배열에 연결된 모든 노드의 정보를 담아줬는데, 그렇게 하면 지우는 노드를 처리할 때 복잡해져서 자식 노드 정보만 넣게끔 바꿨다.

 

 

프로그램 동작

---

(위에서 입력부분은 설명했으니 입력부분은 넘기겠다.)

이 문제에서 원하는건 트리의 순회가 아니라, 트리의 요소를 지우고 리프 노드의 개수를 찾는 것이다.

그래서 노드를 지우는 계산부터 한다.

 

1. 지울 노드부터 아래로 순회를 시작한다.

방문한 노드의 visit 값은 true로 바꿔준다.

그리고 해당 노드의 자식 노드의 값으로 순회 함수를 다시 시작해준다.▼

 

 

3과 4로 함수를 시작해주지만 3과 4에는 자식 노드가 없으므로 지우는 함수는 3과 4의 visit을 true로 만들고 종료된다.▼

 

 

2. 이제 노드를 지우는 과정은 끝났으니 리프 노드를 찾기위해 트리를 순회해본다.

1은 이미 방문했으므로 다음엔 2로 간다.

0이 리프 노드인지 아닌지 판별은 자식 노드의 개수가 몇 개인지로 했다.

자식 노드의 개수가 0개면 리프노드다.

그런데 문제가 있다.

그림 처럼 노드가 지워지는 경우도 있다는 것이다.

0의 자식노드는 원래대로라면 2지만, 지금은 하나가 지워져서 자식 노드가 1개가 된다.

어차피 리프 노드는 아니지만 이렇게 자식 노드가 지워져서, 현재 노드가 리프 노드가 되는 경우도 있게 된다.

그래서 만약 자식 노드에 지운 노드가 포함되어 있다면 자식 노드 개수에서 하나를 빼준다.

그렇게 하면 문제 없이 판별할 수 있다.▼

 

 

이렇게 리프 노드를 판별해 가며 리프 노드의 개수를 세주면 된다.▼

 

 

리프 노드는 2번 노드 하나다.

 

3. 부모 노드도 없고, 자식 노드도 없는 단일 노드들도 리프 노드에 해당하므로 N-1번 까지 dfs를 돌려본다.

 

 

Swift 코드

---

let N = Int(readLine()!)!
var node = readLine()!.split(separator: " ").map { Int(String($0))! }
let delete = Int(readLine()!)!
var visit = Array(repeating: false, count: N)
var childTree = Array(repeating: [Int](), count: N)
var answer = 0
for i in 0..<N {
    if node[i] == -1 {
        continue
    }
    childTree[node[i]].append(i)
}


func delete(_ del: Int) {
    visit[del] = true
    for i in childTree[del] {
        if visit[i] == false {
            delete(i)
        }
    }
}

func dfs(_ num: Int) {
    if visit[num] == true {
        return
    }
    var tmp = childTree[num].count
    visit[num] = true
    if childTree[num].contains(delete) {
        tmp -= 1
    }
    if tmp == 0 {
        answer += 1
    }
    for i in childTree[num] {
        if visit[i] == false {
            dfs(i)
        }
    }
}

delete(delete)
for i in 0..<N {
    dfs(i)
}
print(answer)