BOJ - 2583) 영역 구하기

<BOJ 2583 영역구하기>

모눈 종이 위의 좌측 하단의 좌표와 우측 상단의 좌표가 주어진다. 주의해야할 점은, 이 좌표를 그대로 배열에 적용하면 모눈종이에 표시된 영역과 일치 하지 않게 된다. ex) (1,1) (2,5) 의 경우, 배열에 그대로 적용하게 된다면 2x5 의 행렬이 되어, 모눈종이 상의 1x4 의 영역과 상이하다. 따라서, 입력 받을시 배열에 적합하게 바꾸어준 후, 일반적인 방법의 DFS 알고리즘을 적용하면 어렵지 않게 해결이 가능하다.

 

입력 받음과 동시에, DFS 에 적용하기 쉽도록 영역의 정보를 배열로 만들어 준다.

DFS 알고리즘을 통하여 영역 외의 부분을 체크하고, 영역이 총 몇 개가 있는지 도출한 뒤, 분할된 영역의 수를 저장한 벡터를 sort 함수를 통하여 오름차순으로 정렬해준 뒤 출력한다.