글 읽기 - 게시판 예제는 모두 맞습니다. 반례 부탁드립니다.

dudwls901 2년 전 0

중위순회로 풀진 않았고,

왼쪽 부트리의 노드 수, 오른쪽 부트리의 노드 수를 이용해 부모 노드의 x값을 구해놓고, 이를 기준으로

부모 노드 a

왼쪽 자식 노드 b

오른쪽 자식 노드 c

b의 x좌표 = a의 x좌표 - b의 오른쪽 부트리 노드 수

c의 x좌표 = a의 x좌표 + c의 왼쪽 부트리 노드 수

위 방식으로 노드들의 x 좌표를 구하고 동일한 뎁스에서 minX, maxX로 뎁스별 width를 구해 답을 갱신하였습니다.

게시판 케이스는 모두 맞는데 제가 고려하지 못한 케이스가 어떤 게 있을까요,,

import java.util.*

val br = System.`in`.bufferedReader()

fun getIntGraph() = br.readLine().split(' ').map { it.toInt() }
lateinit var leftInDegree: IntArray
lateinit var rightInDegree: IntArray
lateinit var parent: IntArray
lateinit var xArr: IntArray
lateinit var edge: Array<IntArray>
var answer=Pair(1,1)
var root=0

fun bfs(n: Int){
    val q: Queue<Int> = LinkedList()

    q.add(root)
    xArr[root] = leftInDegree[root]+1
//    println("1 ${xArr[root]}")
    var depth=2
    while(q.isNotEmpty()){
        val size = q.size
        var minX = n+1
        var maxX = 0
        for(i in 0 until size) {
            val cur = q.poll()
            for (next in edge[cur]) {
                if(next<0) continue
                //왼쪽 부트리
                if (parent[next] < 0) {
                    xArr[next] = xArr[-parent[next]] - rightInDegree[next] - 1
                }
                //오른쪽 부트리
                else {
                    xArr[next] = xArr[parent[next]] + leftInDegree[next] + 1
                }
                minX = minX.coerceAtMost(xArr[next])
                maxX = maxX.coerceAtLeast(xArr[next])
                q.add(next)
//                println("$depth ${xArr[next]} $minX $maxX")
            }
        }
        val width = maxX-minX+1
        if(answer.second<width){
            answer = Pair(depth,width)
        }
        depth++
    }
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val n = br.readLine().toInt()
    leftInDegree = IntArray(n+1)
    rightInDegree = IntArray(n+1)
    parent = IntArray(n+1)
    xArr = IntArray(n+1)
    edge = Array(n+1){IntArray(2)}
    repeat(n){
        val (x,l,r) = getIntGraph()
        edge[x][0]=l
        edge[x][1]=r
        if(l>=0) {
            leftInDegree[x]++
            parent[l] = -x
        }
        if(r>=0){
            rightInDegree[x]++
            parent[r] = x
        }
    }
    //preset
    //노드의 왼쪽 부트리 총 갯수, 오른쪽 부트리 총 갯수 저장
    //루트 노드 저장
    for(i in n downTo 1){
        //왼쪽 부트리인 경우
        if(parent[i]<0){
            leftInDegree[-parent[i]]+= leftInDegree[i]+ rightInDegree[i]
        }
        //오른쪽 부트리인 경우
        else if(parent[i]>0){
            rightInDegree[parent[i]]+= leftInDegree[i]+ rightInDegree[i]
        }
        //root
        else{
            root=i
        }
    }
    //solve
    bfs(n)

    //output
    write("${answer.first} ${answer.second}")

    close()
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판 예제는 모두 맞습니다. 반례 부탁드립니다.

dudwls901 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말