Tree8 [백준 Gold 1] 2213 트리의 독립집합 - Java 문제링크 : https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 접근 과정 : 이전에 풀었던, '트리에서의 다이나믹 프로그래밍' 접근을 통해서 문제를 해결하려고 했다. 추가적으로 고민했던 부분은 독립 집합의 원소들을 추적하는 부분이었다. 결국 현재 정점의 독립 집합 포함 여부에 따라서 연결된 다음 정점의 포함여부가 결정되기에, 이 부분을 고려해서 작성했다. DP[][] : i번 정점의 독립집합 포함 여부 , [n+1.. 2022. 1. 6. [백준 Gold 1] 1949 우수 마을 - Java 문제링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 접근 과정 : 특정 마을이 우수 마을인지 아닌지를 기준으로하는 DP를 사용했다. DP[][] : i 마을이 우수 마을인 경우(1) / 우수 마을이 아닌 경우(0) 의 우수 마을들의 인구 총합 마을간의 연결 관계는, town 클래스를 생성해서 사용했다. '트리에서의 다이나믹 프로그래밍' 을 풀어보았다면 어렵지 않게 해결할 수 있다. 소스 코드 및 결과 : package BOJ;.. 2022. 1. 5. [백준 Gold 4] 20040 사이클 게임 - Java 문제링크 : https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 접근 과정 : 분리 집합으로 접근하면 간단하다. 연결 정보에 따라서 집합으로 합쳐주고. 만약 집합의 번호가 같으면 사이클이 형성된다!! 사이클이 형성될 때, i를 리턴한다. +++ 비슷한 문제 : https://rays-space.tistory.com/74 [백준 Gold 4] 4803 트리 - Java 문제링크 : https://www.acmicpc.net/problem/480.. 2022. 1. 3. [백준 Gold 4] 4803 트리 - Java 문제링크 : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 접근 과정 : 사이클이 형성되지 않은 트리만을 찾아서 갯수를 세주면 된다. 간선이 연결될 때, 만약 두 정점중 하나가 사이클에 포함되어 있거나, 해당 간선으로 사이클을 형성하게 되는 경우를 확인해야 한다. 트리의 루트 노드를 기억하고, 이를 이용해서 사이클을 확인했다. A,B를 잇는 간선이 있을 때, roo[A] == root[B] 라면 이는 사이클을 형성하게 된다... 2022. 1. 3. 이전 1 2 다음
