[C++] 백준 2667번 풀이 ( 단지번호 붙이기 )

- 문제

• 링크 : https://www.acmicpc.net/problem/2667

• 정사각형 모양의 지도가 주어지고, 그 지도안에는 집이 있는 곳의 위치가 1로 나타내어져있다.
  이러한 지도에서 대각선을 제외한 상, 하, 좌, 우 방향으로 집이 연결되어있는 곳을 하나의 단지로 볼 때

  • 지도에 표시되어있는 단지의 수
  • 각 단지에 속해있는 집의 수

  를 출력하는 프로그램을 작성하는 문제.

---

- 입력 및 출력

[ 입력 ]

• 첫번째 줄에 지도의 크기 입력 (5 ≤ N ≤ 25 )
• 두번째 줄부터 N줄동안 집이 존재하는지에 대한 여부 ( 0 or 1 ) 입력

[ 출력 ]

• 첫번째 줄에는 지도에 표시되어있는 단지 수 출력
• 두번째 줄부터 각 단지 내 집의 수를 오름차순으로 한줄에 하나씩 출력.

---

- 문제 풀이

• 이번 문제는 인접행렬로 주어져있는 그래프를 탐색해 1이 상, 하, 좌, 우로 인접해있는 덩어리별로 단지를 잘라내는 문제이다.

• 나는 이번 문제를 아래와 같이 접근했다.

  1. 지도를 모두 순회하면서 ( N * N ) 방문하지 않았고, 집이 있는 경우 (1) 그 위치에 대해 DFS 탐색을 진행하도록 하였다.
     
     
  2. 단지의 수는 1번 과정에서 한 점에 대해 DFS 가 시작할 때 1씩 증가해주었다.
     => 한 점에 대해서 DFS 로 단지 하나를 전부 찾았다면, 그 다음에 이 단지에 속해있는 집은 접근하지 않으니 단지의 개수 확인 가능.
     
     
  3. 각 단지별 속해있는 집의 개수는 DFS 탐색을 하는 함수가 한번씩 불릴때마다 집의 개수가 1개씩 증가하는 것이므로 함수가 불리지마자 값을 1 증가하고, DFS 탐색을 끝낸 후 1번 과정의 반복문으로 돌아갔을 때 값을 vector 에 저장해주었다.
     => vector 사용 이유 : 출력 시 오름차순으로 정렬해야하기 때문에 vector 를 사용함.
     
     
  4. 지도의 모든 위치에 대해 탐색을 마쳤다면 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;

}