공부공간

www.acmicpc.net/problem/14889 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net N명이 속한 축구팀을 N/2 N/2씩 나누기위해 비트연산을 이용한다. 0~(1

모눈 종이 위의 좌측 하단의 좌표와 우측 상단의 좌표가 주어진다. 주의해야할 점은, 이 좌표를 그대로 배열에 적용하면 모눈종이에 표시된 영역과 일치 하지 않게 된다. ex) (1,1) (2,5) 의 경우, 배열에 그대로 적용하게 된다면 2x5 의 행렬이 되어, 모눈종이 상의 1x4 의 영역과 상이하다. 따라서, 입력 받을시 배열에 적합하게 바꾸어준 후, 일반적인 방법의 DFS 알고리즘을 적용하면 어렵지 않게 해결이 가능하다. 입력 받음과 동시에, DFS 에 적용하기 쉽도록 영역의 정보를 배열로 만들어 준다. DFS 알고리즘을 통하여 영역 외의 부분을 체크하고, 영역이 총 몇 개가 있는지 도출한 뒤, 분할된 영역의 수를 저장한 벡터를 sort 함수를 통하여 오름차순으로 정렬해준 뒤 출력한다.

필요한 배추 흰지렁이의 개수를 구하는 문제이다. 인접한 배추끼리는 이동이 가능하므로 DFS를 돌면서 상하좌우의 조건을 걸어서 탐색하게 하였다. 즉 배열 전체를 돌면서, 탐색안한곳을 시작하면 배추 흰지렁이 개수를 증가시키고 그 지렁이가 갈수있는 모든 경로의 Visit 배열을 True바꾸어주었다.