[BAEKJOON][실버1] - 단지번호 붙이기(2667번)

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

https://coder-angrybird.tistory.com/26

[BAEKJOON][실버1] - 안전영역(2468번)

저번 2468번 안전영역 문제와 매우 유사한 문제이다.

2468번 문제에 영역을 1과 0으로 표시했을때 영역이 몇개가 있는지 찾는 DFS 알고리즘의 사방탐색 과정에 대해 자세히 써 놓았다.

2468과 비교해서 2667번 문제의 특징은 영역의 갯수 뿐 아니라 해당 영역에 1이 몇개가 있는지까지 찾고,
또 찾은 영역의 갯수를 오름차순 정렬하여 출력해야한다는 것이다.

DFS 알고리즘 자체는 2468번과 완전히 똑같으니 크게 언급하지 않겠다.
우선 영역의 총 개수는 DFS가 DFS를 호출한 것은 제외하고
좌표 평면에서 DFS를 호출한, 전체 코드에서 DFS가 몇번 호출했는지를 확인하면 알 수 있었다.

그리고 여기서 말하는 집이 몇채인지, 즉, 각 영역에서 1의 개수는 DFS가 재귀 내에서 몇번 호출되었는지를 확인하면 알 수 있다.

1. DFS가 최초 호출되어서 재귀탐색까지 모두 마치고 나올때 비로소 한 영역이 모두 탐색이되어 영역이 끝난다.
2. 따라서 DFS가 재귀로 호출되는 경우는 그 한 영역에서 탐색 중 1이 보이는 경우이다.
3. DFS가 몇 번 재귀로 호출되었는지 알면 집의 수를 알 수 있다.

DFS의 코드이다.
보면 DFS를 재귀로 만드는 10번라인 아래 11번 라인에 house_num++를 볼 수 있다.
DFS가 재귀로 호출 되는 횟수를 카운트하기 위해 만든 변수이다.

이 부분은 정렬알고리즘이다. 자바의 라이브러리를 쓰는 것도 좋지만, 공부를 위해 직접정렬을 구현하였다.
여기서 주의할 점은 2번과 4번 라인이다.
배열이 있을때, 예를 들어 인덱스 값이 0,1,2,3을 갖는 크기 4의 배열이 있다고 하면
0과 1, 1과 2, 2와 3을 비교하기에 i = 0 에서 시작해서 num_area -1로 끝나는 것이고, j 는 j+1로 시작해서 num_area로 끝나는 것이다.

또한 전체 코드의 주석을 보면 알 수 있겠지만, 오름차순 정렬을 위해 집의 개수를 저장하는 배열 house[]의 배열 크기는
집의 개수의 최대치인 영역에서 모든 좌표의 개수로 초기화 해놓았다.

말인즉슨 단지의 수만큼 만 각 단지의 집의 개수가 house 배열에 저장되어 있으니, house 배열의 남은 저장공간의 대부분은 빈공간(0)인 것이고, num_area 자리에 절대 house.length를 사용하지 않도록 주의한다.

아래는 전체 코드와 코드가 올라가있는 깃허브 주소이다.

https://github.com/Headfish96/Online-Judge

GitHub - Headfish96/Online-Judge: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://gi