Algorithm/BaekJoon

[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..

[JAVA] 백준 1774번 : 우주신과의 교감

문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 해결 방법 크루스칼 알고리즘을 활용해서 풀었다. 크루스칼이란 간단하게만 설명하면, 정점들과 이어진 간선의 거리를 기준으로 정렬한 뒤에 정렬된 순서대로 접근하여 유니온-파인드를 활용하여 앞의 두 정점이 연결되어 있지 않으면 연결시켜주는 방식으로써 가장 짧은 거리의 간선이 제일 앞으로 정렬되어 있기 때문에 제일 짧은 경로를 만들어 낼 수 있다. 문제에서 이미 연결된 통로로 주어지는 값들은 거리를 0으로 설정해서 리스트에 입력해주는 방..