[C++] 백준 2667번 단지 붙이기 (Silver 1)

풀이

DFS 접근 법을 통해 해결하면 된다. 전형적인 DFS 문제라고 한다...

1. 깊이우선 탐색을 통해 처음 1을 발견하면, 모든 연결된 1을 방문하면서 넓이를 +1 해주면 된다.

2. 처음 발견한 곳은 visited[row][col] 어레이를 통해 확인하면 된다.

3. 재귀 방식 dfs(int r, int c)과 스택 방식 dfs_stk(int r, int c) 모두 테스트 해보았다.

 

리뷰

그래프 문제 풀려고 선택한 문제인데, 아무 생각 없이 DP로 접근했다가 후퇴한 문제다...

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;
 
int map[25][25];
int visited[25][25];
vector<int> cntVec;
 
//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int N;
int cnt;
 
void dfs(int r, int c){
 
    for(int i = 0; i<4; i++){
        
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr>=N || nr<0 || nc>=N || nc<0) continue;
        
        if(visited[nr][nc]==0 && map[nr][nc]==1){   //방문 안했고 집이 있으면
            visited[nr][nc] = 1;                    //방문했다고 표시하고
            cnt+=1;                                 //집 개수 세기
            dfs(nr,nc);
        }
    }
 
}
 
void dfs_stk(int r, int c) 
{
    stack<pair<int, int>> stk;
    stk.push({r, c});

    while (!stk.empty()) {
        pair<int, int> v = stk.top();
        stk.pop();
        
        if (visited[v.first][v.second]) continue;

        visited[v.first][v.second] = 1;
        cnt+=1; 
        for (int i = 0; i < 4; i++) {
            int nr = v.first + dr[i];
            int nc = v.second + dc[i];
            
            if(nr>=N || nr<0 || nc>=N || nc<0) continue;
            
            if(visited[nr][nc]==0 && map[nr][nc]==1){   //방문 안했고 집이 있으면
                stk.push({nr, nc});                   
            }
        }
    }
}
 
int main(){
    
    int res=0;
    freopen("2667.txt", "r", stdin);

    cin >> N;
    string str;
    
    for(int i = 0; i<N; i++){
        cin >> str;
        for(int j = 0; j<str.length(); j++){            //입력 주의
            visited[i][j] = 0;
            
            if(str[j] == '1'){
                map[i][j] = 1;
            }
            else map[i][j] = 0;
        }
    }
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            
            if(map[i][j]==1 && visited[i][j]==0){
                // visited[i][j] = 1;
                cnt = 0;                        //처음은 시작점 포함하므로 1로 초기화
                // dfs(i,j);
                dfs_stk(i,j);
                cntVec.push_back(cnt);
                res++;                          //단지 그룹 1개 탐색 끝남
            }
        }
    }
    
    sort(cntVec.begin(), cntVec.end());
    cout << res << "\n";
    
    for(int i = 0; i<cntVec.size(); i++){
        cout << cntVec[i] << "\n";
    }
 
    return 0;
}