[백준 / BOJ] 2233 사과나무

문제 

출처 : www.acmicpc.net/problem/2233

2233번: 사과나무

정점의 개수와 벌레가 만드는 이진수를 입력받고, 정상적인나무를 최소화한상태로 썩은나무를 모두 없애는 정점을 구하는 문제다.

 

풀이

그래프 구조를 만들필요없이 해당노드의 등장 순서만 알고있다면 풀리는 문제다. 

 

입력을 보면, 벌레가 만드는 이진수가 깊이우선탐색의 순서와동일한것을 알수있다.

(해당 노드에서 끝까지 간후 더이상 갈수없을경우, 부모로 올라감)

-이진수에 따라 자식과 부모관계를 만들어주기위해, par[] 배열을 선언해 부모와 자식관계를 정해준다.

(par[3] = 2) -> 3의 부모는 2임

 

0 과 1을 내리고 올리는 스위치라고 생각하자

1. 현재 이진수가 0 일경우, 저장되어야하는 노드를 저장해주고 해당 노드로 내려간다.

2. 현재 이진수가 1일경우, 미리 만들어놓은 par배열을 참조해, 부모를 저장해주고, 다시 부모로 올라간다.

 

이진수의 크기만큼 위를 반복하면, 각 노드의 등장 인덱스를 알수있다.

예를들어 (1번노드는 첫번째로등장하고 마지막으로 등장한다.)

마지막으로 X, Y를 입력받고 이중반복을 통해 X와 Y의 부모를 역순으로 탐색하며, X,Y에서 가장 가까운 층의 공통 부모를 찾아주면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2233%20%EC%82%AC%EA%B3%BC%EB%82%98%EB%AC%B4/main.cpp

devxb/JJUNalgo