[C++] BOJ_2667 단지 번호 붙이기

문제: 백준 2667 (c++)

풀이과정

---

이 문제는 dfs 또는 bfs로 풀 수 있는데 아래의 코드는 dfs로 푼 코드이다.

주어진 배열을 탐색한다는 느낌으로 접근하면 쉬울 것이다.

maze 문제 (미로 탐색 문제)와 비슷하다.

코드를 분리하여 보면,

---

int n ;
int cnt1 = 0 ;
int cnt2 = 0 ;

int board[26][26] ;
int mark[26][26] = {0};

int dx[4] = {1, 0, -1, 0} ;
int dy[4] = {0, 1, 0, -1} ;

vector<int> v ;

입력 받는 지도의 배열과 방문 여부를 표시할 배열을 선언했고

탐색을 해야 하기에 dx,dy 라는 방향키 배열을 선언했다.

---

void dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + dx[i] ;
        int ny = y + dy[i] ;

        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
            if(board[nx][ny] == 1 && mark[nx][ny] == 0){
                mark[nx][ny] = 1 ;                   
                cnt2++ ;                               
                dfs(nx, ny);
            }
        }
    }

}

dfs 함수인데 4개의 방향으로 탐색하도록 해주었다

조건문을 이용하여 범위가 벗어나지 않을 경우, 탐색한 위치가 아직 방문하지 않았고 아파트일 경우,

이어서 dfs 탐색하도록 해주었다.

---

int main(){

    cin >> n ;

    for(int i = 0; i < n; i++){
        string s ;
        cin >> s ;
        for(int j = 0; j < n; j++){
            board[i][j] = s[j] - '0' ;
        }
    }
    
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] == 1 && mark[i][j] == 0){
                mark[i][j] = 1 ;
                cnt2 = 1 ;
                dfs(i, j) ;
                cnt1++ ;
                v.push_back(cnt2) ;
            }
        }
    }

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

    cout << cnt1 << '\n' ;

    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n' ;
    }
    
}

입력 받는 지도 배열을 string으로 받기 때문에 변환을 해야한다는 것을 놓치면 안된다.

지도에서 방문하지 않았고, 위치가 아파트일 경우 dfs 탐색을 진행했다.

또한 cnt1은 단지의 수, cnt2는 아파트의 수이기에 구분을 하여 cnt2는 vector를 이용하여 수를 세주었다.

---

전체 코드이다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;

    int n ;
    int cnt1 = 0 ;
    int cnt2 = 0 ;

    int board[26][26] ;
    int mark[26][26] = {0};

    int dx[4] = {1, 0, -1, 0} ;
    int dy[4] = {0, 1, 0, -1} ;

    vector<int> v ;


void dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + dx[i] ;
        int ny = y + dy[i] ;

        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
            if(board[nx][ny] == 1 && mark[nx][ny] == 0){
                mark[nx][ny] = 1 ;                   
                cnt2++ ;                               
                dfs(nx, ny);
            }
        }
    }

}

int main(){

    cin >> n ;

    for(int i = 0; i < n; i++){
        string s ;
        cin >> s ;
        for(int j = 0; j < n; j++){
            board[i][j] = s[j] - '0' ;
        }
    }
    
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] == 1 && mark[i][j] == 0){
                mark[i][j] = 1 ;
                cnt2 = 1 ;
                dfs(i, j) ;
                cnt1++ ;
                v.push_back(cnt2) ;
            }
        }
    }

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

    cout << cnt1 << '\n' ;

    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n' ;
    }
    
}