[KOI 1996 초등부] 2667번-단지번호붙이기

중요 지식

---

DFS - 인접한 주택을 탐색하기 위함

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int map[25][25];
int N;

void DFS(int x, int y, int &num){
    int xl[4] = {1, 0, -1, 0};
    int yl[4] = {0, 1, 0, -1};
    int xi, yi;

    map[x][y] = 0;
    num++;

    for(int i = 0; i < 4; i++){
        xi = x + xl[i];
        yi = y + yl[i];

        if((xi >= 0 && xi < N) && (yi >= 0 && yi < N) && map[xi][yi] == 1) {
            DFS(xi, yi, num);
        }
    }
}

int main(){
    vector<int> numbers;

    cin >> N;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(map[i][j] == 1){
                int num = 0;
                
                DFS(i, j, num);
                numbers.push_back(num);
            }
        }
    }

    sort(numbers.begin(), numbers.end());

    printf("%d\n", numbers.size());
    for(const int& num : numbers){
        printf("%d\n", num);
    }

    return 0;
}

풀이

---

 

1. 2차원배열 map에 주택의 정보를 저장하고, 

2-1. map을 하나하나 검사하는데 주택이 나온다면 상하좌우 인접주택을 검사하는 DFS함수를 실행한다

2-2. DFS함수는 인접 주택을 방문할 때마다 num에 +1을 하고 방문한 주택은 0으로 설정한다

2-3. 구해진 num은 vector인 numbers에 저장

3. numbers를 정렬한 뒤 사이즈와 요소를 출력한다

 

질문1) DFS함수의 인자중 int &num의 정체는?

DFS함수를 통해서 주택수를 구해야 하지만 이미 재귀함수로써 사용되고 있어서 반환값으로 설정하기 보다는 래퍼런스(&)를 이용하여 직접 값을 참조해서 올려주는게 쉽고 간편하다고 생각했습니다