백준 2667 - 단지번호붙이기 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/2667

풀이전략

1. N의 크기는 5<= N <= 25이므로 시간과 공간은 충분하다.
2. 간 단지별로 속하는 집의 수를 오름차순으로 출력해야한다.
3. DFS를 활용하여 단지를 찾는다.
4. dx(좌우), dy(상하) 배열을 만들어서 인접 칸을 계산한다.
5. 단지를 찾은 부분은 다시 0으로 바꿔주며 중복을 제거한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
// 충분히 잡으면 굳이 경계값 확인할 필요 없음
int mp[27][27];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int cnt = 1;
int res = 0;
void DFS(int r, int c){

    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];

        if(mp[rr][cc]==1){
            mp[rr][cc] = 0;
            DFS(rr, cc);
            cnt++;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    char tmp;
    //// char 형으로 처리한것 유의해서보기
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> tmp;
            mp[i][j] = tmp - '0';
        }
    }
    vector<int> ans;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(mp[i][j] == 1){
                mp[i][j] = 0;
                DFS(i,j);
                res++;     
                ans.push_back(cnt);
                cnt = 1;
            } 
            
        }
    }
    cout<<res<<endl;
    /// 문제에서 단지를 오름차순으로 정리해서 출력하라고하였다.... 이런거 놓치지말자.
    sort(ans.begin(), ans.end());
    for(int i=0; i<ans.size(); i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

소감

먼저 문제 input이 띄어쓰기가 안되어있기 때문에 하나씩 구분하기위해 문자를 char형응로 바꿔어서 처리했다. 따라서 받은 input에 '0'을 빼주어 int형으로 타입을 바꾸어 주었다. 또한 문제에서 단지를 오름차순으로 출력하라고 하였지만 나는 이걸 캐치하지 못하였다. 역시 문제를 제대로 읽는게 제일 중요하다.