74. C++ 백준 2667 단지 번호 붙이기 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 단지번호 붙이기  C++ 백준 2667번 입니다.

최종 코드는 글의 상단과 하단 둘 다 넣었습니다.

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

2667번: 단지번호붙이기

 

 

C++ 백준 2667번 전체 코드입니다.

#include <iostream>
#include <algorithm>
#define MAX 25
using namespace std;
int graph[MAX][MAX] = {0,};
int complex[MAX] = {0,};
int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};
int N;

//DFS
int DFS(int i, int j){
    graph[i][j] = 0;
    int cnt = 1;
    for(int k = 0; k < 4; k++){
        int x = i + x_dir[k];
        int y = j + y_dir[k];
        if (0 <= x and x < N and 0 <= y and y < N){
            if (graph[x][y] == 1){
                cnt += DFS(x, y);
            }
        }
    }
    return cnt;
}
int main(){
    cin >> N;
    string nums;
    //그래프 생성
    for (int i = 0; i < N; i++){
        cin >> nums;
        for (int j = 0; j < N; j++){
            graph[i][j] = nums[j] - '0';
        }
    }

    //단지내의 새대 수 저장
    int cnt = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (graph[i][j] == 1) {
                complex[cnt] = DFS(i, j);
                cnt++;
            }
        }
    }

    //단지 오름차순으로 정렬
    sort(complex, complex+cnt);

    //출력
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << complex[i] << endl;

    return 0;
}

 

총 단지수와, 단지내 집의 수를 오름차순으로 하나씩 출력하는 문제입니다.

그래프의 전체 노드를 순서대로 방문합니다.

1. 만약 방문하지 않은 단지라면 총 단지 수를 1개 늘려주고,

DFS나, BFS를 이용하여 단지내 집의 개수를 찾고, 저장합니다.

2. 만약 방문했던 단지라면 방문하지 않고 다음 노드가 방문한 단지인지 확인합니다.

위의 직관을 갖고 문제를 풀어봅시다.

 

먼저 그래프를 입력 받습니다.

//그래프 생성
for (int i = 0; i < N; i++){
    cin >> nums;
    for (int j = 0; j < N; j++){
        graph[i][j] = nums[j] - '0';
    }
}

 

이 포스트에서는 DFS를 통해 문제를 풀게 됩니다.

현재 노드에서 탐색할 다음 노드의 좌표인 x, y값을 표현하기 위한 행렬을 작성합니다.

int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};

 

참고로 x, y 좌표는 이런식으로 표현할 예정입니다.

int x = i + x_dir[k];
int y = j + y_dir[k];

코드를 읽어보시면 아시겠지만.

좌표 값으로 상,하,좌,우로 움직이는 경우가 되므로

x, y에 1 혹은 -1 을 더해서 조합하는 방식입니다.

 

그래프 탐색 알고리즘인 DFS를 구현해봅시다.

재귀함수 형식으로 구현했습니다.

//DFS
int DFS(int i, int j){
    graph[i][j] = 0;
    int cnt = 1;
    for(int k = 0; k < 4; k++){
        int x = i + x_dir[k];
        int y = j + y_dir[k];
        if (0 <= x and x < N and 0 <= y and y < N){
            if (graph[x][y] == 1){
                cnt += DFS(x, y);
            }
        }
    }
    return cnt;
}

먼저 방문한 노드는 방문처리 하고 다음에 다시 방문하지 않도록 0으로 만들어 주고,

새 노드를 방문 할 때마다 함수가 실행 되므로, 함수 실행시 세대수를 1로 추가해 줍니다. (마지막에 더해서 출력 예정)

graph[i][j] = 0;
int cnt = 1;

여기에서 DFS의 입력값은 무조건 방문하지 않은 상태에서만 호출할 것이기 때문에

위의 코드는 문제가 없습니다.

 

다음에 방문할 노드의 좌표를 만들어줍니다.

int x = i + x_dir[k];
int y = j + y_dir[k];

 

좌표가 그래프 상에서 벗어나는지 확인하고, 벗어나지 않고,

방문가능한 노드라면 방문합니다.

if (0 <= x and x < N and 0 <= y and y < N){
    if (graph[x][y] == 1){
        cnt += DFS(x, y);
    }
}

여기서 cnt는 단지 내 집의 개수를 저장하기 위한 변수이고,

DFS 함수는 방문한 집들의 개수를 재귀적으로 cnt에 저장하고, 리턴하게 됩니다.

        if (0 <= x and x < N and 0 <= y and y < N){
            if (graph[x][y] == 1){
                cnt += DFS(x, y);
            }
        }
    }
    return cnt;
}

 

DFS의 코드입니다.

//DFS
int DFS(int i, int j){
    graph[i][j] = 0;
    int cnt = 1;
    for(int k = 0; k < 4; k++){
        int x = i + x_dir[k];
        int y = j + y_dir[k];
        if (0 <= x and x < N and 0 <= y and y < N){
            if (graph[x][y] == 1){
                cnt += DFS(x, y);
            }
        }
    }
    return cnt;
}

 

단지수를 저장하기 위한 변수, 단지별 세대수를 저장하기 위한 행렬을 선언하고

그래프의 모든 노드를 하나씩 방문 가능한지 살피며

방문가능하면 DFS를 통해 방문하여, 세대수를 저장하고 단지수를 하나 늘려줍니다.

//단지내의 새대 수 저장
int cnt = 0;
for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
        if (graph[i][j] == 1) {
            complex[cnt] = DFS(i, j);
            cnt++;
        }
    }
}

 

이후 세대수를 오름차순으로 정렬하고, 단지수, 세대수를 출력하면 됩니다.  

//단지 오름차순으로 정렬
sort(complex, complex+cnt);

//출력
cout << cnt << endl;
for (int i = 0; i < cnt; i++) cout << complex[i] << endl;

 

단지번호 붙이기 백준 2667번 C++ 최종 코드입니다.

#include <iostream>
#include <algorithm>
#define MAX 25
using namespace std;
int graph[MAX][MAX] = {0,};
int complex[MAX] = {0,};
int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};
int N;

//DFS
int DFS(int i, int j){
    graph[i][j] = 0;
    int cnt = 1;
    for(int k = 0; k < 4; k++){
        int x = i + x_dir[k];
        int y = j + y_dir[k];
        if (0 <= x and x < N and 0 <= y and y < N){
            if (graph[x][y] == 1){
                cnt += DFS(x, y);
            }
        }
    }
    return cnt;
}
int main(){
    cin >> N;
    string nums;
    //그래프 생성
    for (int i = 0; i < N; i++){
        cin >> nums;
        for (int j = 0; j < N; j++){
            graph[i][j] = nums[j] - '0';
        }
    }

    //단지내의 새대 수 저장
    int cnt = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (graph[i][j] == 1) {
                complex[cnt] = DFS(i, j);
                cnt++;
            }
        }
    }

    //단지 오름차순으로 정렬
    sort(complex, complex+cnt);

    //출력
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << complex[i] << endl;

    return 0;
}

 

제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.

https://open.kakao.com/o/guGhqGAg

알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)

 

 

 단지번호 붙이기 백준 2667번 C++  풀이 이었습니다.

감사합니다.