문제 입력 출력 문제링크 분석 배열이 Q번의 연산마다 변화하기 때문에 주기적으로 상태를 체크해야 한다. 작업 1번은 무작위로 특정 위치에(다만 알파벳이 적히지 않은 칸들에 한해서) 알파벳을 적는다. 작업 2번은 K개 이상의 연결 요소가 존재한다면 그 연결 요소를 지운다. 핵심은 크기가 K 이상의 연결 요소를 찾는 방법이다. 작업 2번이 진행되고 새롭게 적은 문자에 의해 K 이상의 연결 요소가 탄생할 수 있다. 즉, 작업 1번에서 추가되는 위치를 기점으로 K개 이상의 연결 요소가 탄생하는지 알면 된다. 이를 위해 Union-Find기법을 이용하여 알파벳이 적히는 위치를 기점으로 상하좌우에서 적힌 알파벳과 같다면 집합을 형성하고 그 집합의 개수가 K개가 넘는지 확인하였다. 풀이 핵심코드 std::list C..

문제 문제링크 분석 처음에는 그래프에서 서로소집합의 개수를 찾는 문제로 판단하여 Union-Find 알고리즘을 사용. 문제의 조건에 따라 집합들을 만들고 각 대표의 개수를 세어 해결함. 그러나 막상 풀고나니 DFS/BFS 같은 그래프 탐색 알고리즘을 통해서도 풀 수 있을 것 같았고, 실제로 정해코드는 탐색 알고리즘을 이용하였음. 풀이 Union-Find(혹은 Disjoint Set) 알고리즘은 각 집합을 트리 형태로 나타내어 표현한다. 특이사항으로는 집합 트리의 노드들은 오직 자신의 상위(혹은 최상위)노드의 정보만을 가진다. 예를 들어 {1, 2, 3, 4 , 5} 와 {6, 7} 집합이 존재한다면 다음과 같은 모습이 될 것이다. parent 배열은 x의 상위노드를 저장하는 배열이다. 이 때 parent..