정사각형 모양의 지도가 주어지고, 그 지도안에는 집이 있는 곳의 위치가 1로 나타내어져있다.
이러한 지도에서 대각선을 제외한 상, 하, 좌, 우 방향으로 집이 연결되어있는 곳을 하나의 단지로 볼 때
- 지도에 표시되어있는 단지의 수
- 각 단지에 속해있는 집의 수
를 출력하는 프로그램을 작성하는 문제.
[ 입력 ]
- 첫번째 줄에 지도의 크기 입력 (5 ≤ N ≤ 25 )
- 두번째 줄부터 N줄동안 집이 존재하는지에 대한 여부 ( 0 or 1 ) 입력
[ 출력 ]
- 첫번째 줄에는 지도에 표시되어있는 단지 수 출력
- 두번째 줄부터 각 단지 내 집의 수를 오름차순으로 한줄에 하나씩 출력.
이번 문제는 인접행렬로 주어져있는 그래프를 탐색해 1이 상, 하, 좌, 우로 인접해있는 덩어리별로 단지를 잘라내는 문제이다.
나는 이번 문제를 아래와 같이 접근했다.
- 지도를 모두 순회하면서 ( N * N ) 방문하지 않았고, 집이 있는 경우 (1) 그 위치에 대해 DFS 탐색을 진행하도록 하였다.
- 단지의 수는 1번 과정에서 한 점에 대해 DFS 가 시작할 때 1씩 증가해주었다.
=> 한 점에 대해서 DFS 로 단지 하나를 전부 찾았다면, 그 다음에 이 단지에 속해있는 집은 접근하지 않으니 단지의 개수 확인 가능.
- 각 단지별 속해있는 집의 개수는 DFS 탐색을 하는 함수가 한번씩 불릴때마다 집의 개수가 1개씩 증가하는 것이므로 함수가 불리지마자 값을 1 증가하고, DFS 탐색을 끝낸 후 1번 과정의 반복문으로 돌아갔을 때 값을 vector 에 저장해주었다.
=> vector 사용 이유 : 출력 시 오름차순으로 정렬해야하기 때문에 vector 를 사용함.
- 지도의 모든 위치에 대해 탐색을 마쳤다면 vector 를 오름차순 정렬 후 출력형식에 맞게 출력하면 문제 해결!
이번 문제에서 주의할 점
- 탐색문제 + dx, dy technique 문제이기 때문에 배열의 범위를 넘어서지는 않는지 확인해야함.
- 방문했는지에 대한 정보를 헷갈리지말고 방문 즉시 표시를 해서 여러번 방문하는 일이 없도록 주의해야함.
#include <iostream>
#include <vector>
#include <algorithm>
#define N_MAX 26
using namespace std;
// 지도의 크기 N 선언
int N = 0;
// 단지에 속하는 집의 수 저장 변수 및 배열
int cnt = 0;
vector<int> number_of_house;
// 지도 배열 선언
int map [N_MAX][N_MAX] = {0, };
// 지도의 (i, j) 위치를 방문했는지 확인하는 배열
bool is_visited[N_MAX][N_MAX] = {false, };
// dx, dy technique 에 사용할 변수 선언
int dx[4] = {0, 0, -1, 1}; // 상, 하, 좌, 우
int dy[4] = {-1, 1, 0, 0}; // 상, 하, 좌, 우
// 이동할 위치가 이동할 수 있는 유효한 위치인지 확인
bool InRange(int a, int b) {
// 지도 안에 존재하는 위치인지 확인
bool in_map = 0 <= a && a < N_MAX && 0 <= b && b < N_MAX;
// 이동하고자 하는 위치에 집이 있는지
bool exist_house = (map[a][b] == 1);
// 지도안에 존재하는 위치이고, 집이 있는지에 대한 boolean 값 return
return (in_map && exist_house);
}
// 지도를 하나씩 방문하며 연결된 가구를 하나의 단지로 구분
void Seperate(int a, int b) {
// 이 함수를 실행했다면 집을 하나 방문한 것이므로 count 1 증가
cnt++;
// 움직이고자 하는 좌표 구하기 (상, 하, 좌, 우 모든 방향에 대해서)
for(int i = 0; i < 4; i++) {
int ni = a + dx[i];
int nj = b + dy[i];
// 이동할 수 있는 위치인지와 그 위치를 방문여부 확인
if(InRange(ni, nj) && (!is_visited[ni][nj])) {
// 이동할 수 있는 위치고 아직 방문한 적 없는 위치라면 그 위치에 대해 다시 탐색
is_visited[ni][nj] = true;
Seperate(ni, nj);
}
}
}
// 각 단지에 속하는 집의 수 출력하는 함수
void print_house () {
for(int i = 0; i < number_of_house.size(); i++) {
cout << number_of_house[i] << '\n';
}
}
int main() {
// 지도의 크기 입력
cin >> N;
// 지도에 작성되어있는 N 개의 자료 입력
for(int i = 0; i < N; i ++) {
for (int j = 0; j < N; j++) {
scanf("%1d", &map[i][j]);
}
}
// 단지의 개수를 세는 변수
int result = 0;
// 지도를 하나씩 방문하면서 단지를 구분
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
// 아직 방문하지 않았고, 집이 있는 위치에 대해서만 방문
if((!is_visited[i][j]) && (map[i][j] == 1)) {
cnt = 0;
is_visited[i][j] = true;
Seperate(i, j);
result ++; // 단지 개수 증가
number_of_house.push_back(cnt); // 단지 내에 있는 집의 개수 저장
}
// 나머지 경우에 대해서는 방문했지만 집이 없으므로 탐색을 하지 않은 것이므로 true 저장
is_visited[i][j] = true;
}
}
// 각 단지에 속해있는 집의 수를 오름차순으로 정렬
sort(number_of_house.begin(), number_of_house.end());
// 단지의 수와 각 단지에 속해있는 집의 수 출력
cout << result << '\n';
print_house();
return 0;
}