백준 1068번
https://www.acmicpc.net/problem/1068
문제
생각하기
-
트리의 형태를 DFS를 통해서 탐색하는 문제이다.
-
이 문제의 핵심은 주어지는 값을 배열로 저장했을 경우, index는 노드 번호가 되고 value는 해당 노드의 부모 노드 번호가 된다는 점이다.
-
-1은 항상 루트인것은 맞지만, -1이 항상 제일 앞에 테스트 케이스로 주어지는 것은 아니라는 점을 알아야한다.
동작
for (i in 0 until N) {
arr[i] = st.nextToken().toInt()
// 배열에서 index는 각 노드의 번호가 되고, value는 부모 노드의 번호가 된다.
}
테스트 케이스로 들어오는 값을 배열로 저장한다. 여기서 배열의 index는 노드의 번호를 의미하고, 배열에 담긴 값은 해당 노드의 부모 번호를 의미한다.
// 루트 노드는 항상 -1의 값을 가진다.
val deleteNodeNum = br.readLine().toInt()
// 루트 노드를 제거하면 리프노드는 존재할 수 없다.
if (arr[deleteNodeNum] == -1) {
println(0)
return
}
만약 루트노드로 들어오는 -1의 값을 가지는 노드를 자른다면, 리프 노드는 존재할 수 없으므로 곧 바로 0을 출력하도록 한다.
private fun DFS(startNum: Int) {
isVisited[startNum] = true
// 부모 노드의 번호를 가진 값들로 모두 DFS탐색
for (i in 0 until N) {
if (arr[i] == startNum) {
isVisited[i] = true
DFS(i)
}
}
} // End of DFS
이제 DFS를 통해서 삭제되는 노드번호를 시작으로 DFS탐색으로 노드들을 방문처리해준다.
아까 위에서 말했듯이 배열에서 index는 노드번호 value는 부모의 노드번호라고 설명했다.
그렇다면 시작하는 값을 가져와서 배열 전체를 반복하며, 해당 노드번호 값을 가지는 배열이 있을 경우 재귀를 통해서 탐색하고 탐색된 값은 isVisited 배열로 방문처리를 해준다.
방문처리된 노드번호는 삭제되었다는 것을 의미한다.
// 제거된 노드를 반영하여 자신의 노드 번호를 가지고 있는 노드를 찾는다.
val isParent = BooleanArray(N)
for (i in 0 until N) {
if (arr[i] == -1 || isVisited[i]) continue // 루트 노드는 통과,
isParent[arr[i]] = true
}
이제 삭제한 노드와 같이 잘려나간 노드들은 모두 확인했고, 우리는 리프 노드의 개수를 파악하는게 문제이므로
이제는 남아있는 노드 중에서 각 노드를 부모로 가지는 노드가 있는지를 확인해야한다.
리프노드 특성상 자식이 없으므로 리프노드는 절대 부모가 될 수 없다.
따라서, -1인 루트와, 이미 삭제된 isVisited에 있는 노드를 제외하고
모든 노드의 번호를 true처리 해준다. value는 곧 부모의 번호이므로, value로 들어와있는 번호는 곧 자식이 있다는 것을 의미하기 때문이다.
// 둘다 false인 값
var count = 0
for (i in 0 until N) {
if (isParent[i] == false && isVisited[i] == false) {
count++
}
}
마지막으로 잘리지않은 노드, isVisited가 false이면서, isParent도 false로 둘다 false인 경우에는
해당 노드 번호가 리프노드임을 의미하므로 count를 증가시켜 리프노드의 개수를 파악할 수 있다.
코드
Kotlin
import java.util.*
import java.io.*
private var N = 0
private val arr = IntArray(50)
private val isVisited = BooleanArray(50)
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
N = br.readLine().toInt()
val st = StringTokenizer(br.readLine())
for (i in 0 until N) {
arr[i] = st.nextToken().toInt()
// 배열에서 index는 각 노드의 번호가 되고, value는 부모 노드의 번호가 된다.
}
// 루트 노드는 항상 -1의 값을 가진다.
val deleteNodeNum = br.readLine().toInt()
// 루트 노드를 제거하면 리프노드는 존재할 수 없다.
if (arr[deleteNodeNum] == -1) {
println(0)
return
}
// 시작하는 노드의 번호 -> 지울 노드의 번호
DFS(deleteNodeNum)
// 제거된 노드를 반영하여 자신의 노드 번호를 가지고 있는 노드를 찾는다.
val isParent = BooleanArray(N)
for (i in 0 until N) {
if (arr[i] == -1 || isVisited[i]) continue // 루트 노드는 통과,
isParent[arr[i]] = true
}
// 둘다 false인 값
var count = 0
for (i in 0 until N) {
if (isParent[i] == false && isVisited[i] == false) {
count++
}
}
println(count)
} // End of main
private fun DFS(startNum: Int) {
isVisited[startNum] = true
// 부모 노드의 번호를 가진 값들로 모두 DFS탐색
for (i in 0 until N) {
if (arr[i] == startNum) {
isVisited[i] = true
DFS(i)
}
}
} // End of DFS
