트리

[JAVA] 백준 4256 : 트리

보호되어 있는 글입니다.

[JAVA] 백준 14267 : 회사 문화 1

문제 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 해결 방법 생각보다 까다로웠던 문제였다. 이 문제에서 주의 깊게 봐야 하는 것은 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이라는 것. 처음엔 인접리스트를 구현한 후에 칭찬을 받은 번호부터 칭찬의 수치를 dfs로 탐색하며 업데이트하는 방법을 사용했다. 다음 탐색할 곳을 찾는 것은 단순히 현재 탐색하는 곳보다 숫자가 크면 탐색하는 조건문을 사용했다. 하지만 최초 칭찬의 횟수만큼 계속 탐색을 진행하게 되어 시간 초과가 발생해서 다른 방법..

[JAVA] 백준 15900 : 나무 탈출

문제 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 해결 방법 천천히 문제를 읽어보고 주어진 입력을 손으로 그려보았다. 그 결과 알 수 있는 점은 모든 리프 노드에서 루트 노드까지 거리가 홀수일 경우 성원이가 이길 수 있고, 짝수일 경우 성원이가 질 수밖에 없음을 알 수 있다. 예제 입력 2를 그림판으로 그려본 것인데, 게임 말은 리프노 노드에 위치한다고 했기 때문에 3 과 4에서 시작한다. 각각 2와 1을 거쳐 2칸, 2칸, 즉 총 4칸을 움직여야 모든 게임 말이 제거된다. 그렇기 때문에 모든 리프 노드에서..

[JAVA] 백준 1068 : 트리

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 해결 방법 인접리스트를 활용해서 트리를 구현한 다음 리프노드를 체크해서 개수를 출력하였다. 리프노드(Leaf Node)란? 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드) 라고 한다. 출처 : ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import ja..