분리 집합12 백준 20156 자바 - 기왕 이렇게 된 거 암기왕이 되어라 (BOJ 20156 JAVA) 문제 : boj20156 구현도 빡쌘편이고 함정카드도 꽤 생각하기 힘든 녀석이었다. 역시 항상 20퍼대 이하의 정답률 문제들은 항상 뭔가가 있다. 그리고 요즘 스트릭만 채운다고 실버위주로 풀다가 오랜만에 플래 풀어보니 체감이 확 된다 ㅋㅋㅋ 1. 우선 다른거 다 빼고 동일 스터디 그룹인지 어떻게 알 수 있을지 생각해보자. 이 부분은 간단하다. union-find를 사용해 disjoint set을 파악하면 된다. 입력으로 받은 B와 C가 동일한 그룹인지 확인하려면, B와 C가 같은 그룹내에 속한지 판단만 하면 알 수 있다(일반적으로 union-find를 사용했다면 결국 find(B) == find(C) 라면 동일 그룹이다). 2. 그룹이 해제는 어떻게 해요? 생각할게 너무 많아요! 그룹을 해제하는건 어렵지.. 2022. 3. 8. 백준 20040 자바 - 사이클 게임 (BOJ 20040 JAVA) 문제 : boj20040 N개의 정점이 있는 그래프에 대해 M개의 간선을 순서대로 연결하면서 사이클이 언제 생기는지 파악하면 된다. 즉, 간선을 연결하는 중에 사이클 판정만 할 수 있다면 풀 수 있다. 내 경우엔 union-find를 사용해 disjoint set(분리 집합)에 대해 판단했다. 새로운 간선을 연결했을 때, 연결한 두 정점이 동일한 그룹이라면 사이클이 생긴 경우이므로, 현재까지 연결한 간선의 개수를 카운팅한걸 답으로 출력하면 된다. 모든 간선을 연결해도 사이클이 생기지 않았다면 0을 출력하면 된다. 코드 : github import java.io.DataInputStream; import java.io.IOException; import java.util.Arrays; public clas.. 2022. 1. 24. 이전 1 2 다음
