글 읽기 - 2533 접근 방법에 대한 질문입니다 ㅜ

cuhcuh1 5년 전 1

먼저 제가 생각한 방법을 말씀드리면,

BFS로 1번 노드에서 부터 트리 탐색을 하면서 각 level별 노드의 수와 leaf 노드의 수를 카운트 했습니다.

그리고 level별 노드의 수와 leaf 노드의 수를 가지고 최소의 얼리 어답터 수를 구했습니다.

(1) 기본적으로 n번째는 n - 2번째의 얼리 어답터 수에 n번째 노드 수를 더한 값이다.

(2) n - 2번째 얼리 어답터 수에서 n - 1번째 leaf 노드를 제외한 노드 수를 더한 값일 수도 있다.

(3) n - 2번째 얼리 어답터 수에서 n - 1번째 leaf 노드를 제외한 노드 수에 n번째 leaf 노드를 제외한 수를 더한 값일 수도 있다.

17
1 2
1 3
4 5
4 6
4 7
6 8
8 9
8 10
8 11
11 12
11 13
11 14
11 15
11 16
11 17

과 같은 테스트 케이스도 잘 돌아갑니다. 무엇이 문제일까요...?

    func searchTree() {
        var qu = [(Int, Int)]()
        var posLevel = 1
        var posCnt = 0
        var leafCnt = 0
        var visit = [Bool](repeating: false, count: n)

        qu.append((0, posLevel))
        visit[0] = true
        while qu.count != 0 {
            let (pos, level) = qu.removeFirst()

            if level != posLevel {
                self.level.append(posCnt)
                self.leaf.append(leafCnt)
                posCnt = 0
                leafCnt = 0
                posLevel = level
            }
            posCnt += 1

			var isLeaf = true
            for next in relationship[pos] {
                if visit[next] == false {
                	isLeaf = false
                    visit[next] = true
                    qu.append((next, level + 1))
                }
            }

            if isLeaf == true {
				leafCnt += 1
			}
        }

		self.level.append(posCnt)
		self.leaf.append(leafCnt)
    }

    func getAns() -> Int {
        searchTree()

		var reg = [Int](repeating: 0, count: level.count)
    	reg[0] = level[0]
    	reg[1] = level[1]

    	for i in 2 ..< level.count {
    		reg[i] = min(reg[i - 2], reg[i - 2] + level[i - 1] - leaf[i - 1] - leaf[i]) + level[i]
    		reg[i] = min(reg[i], reg[i - 2] + level[i - 1] - leaf[i - 1])
		}

		print(level)
		print(leaf)
		print(reg)
		return min(reg[level.count - 1], reg[level.count - 2])
    }

sssdongsss 5년 전 0

선생님 해결됨으로 바꿔주시져 - ☆

cuhcuh1 5년 전 0

같은 level에 있는 노드라도 부모 노드에 따라 선택 되어야 하는 노드와 선택되지 않아야 하는 노드가 섞여있는 level이 존재합니다.

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

문제

문제

출처

ICPC

2533 접근 방법에 대한 질문입니다 ㅜ

cuhcuh1 5년 전 1

sssdongsss 5년 전 0

cuhcuh1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말