Union2 [백준 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. [백준 Gold 2] 4195 친구 네트워크 - Java 문제링크 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 접근 과정 : 익숙한 유형이라고 생각했다. 노드의 부모를 알 수 있는 자료구조와, 해당 노드가 부모인 그룹의 수를 저장하는 자료구조를 이용해서 풀이했다. 보통 익숙한 문제에서는 노드를 숫자로 주기때문에, 2개의 배열을 이용해서 쉽게 풀 수 있다. 해당 문제는 String값으로 노드가 주어졌고, 총 몇명의 친구가 주어지는지 확실하지 않았다. 그래서 HashMap으로 노드의 아.. 2021. 12. 28. 이전 1 다음
