[C++] 백준 2667 : 단지 번호 붙이기

문제

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

 

 

풀이

DFS와 BFS로 모두 풀 수 있는 문제였다.

나의 경우 BFS를 연습할 겸 BFS 이용해서 풀었다.

 

1. 일단 문제에서 단지 정보를 공백을 통해 구분해서 주는 것이 아니라 문자열로 주고 있으므로, 문자열로 입력받은 정보를 int 값으로 변환하여 저장해주어야 한다.

 

2. 그리고 아직 방문하지 않은 집을 찾을 때마다 방문 표시를 하며 BFS를 호출한다. 한 번의 BFS 호출 마다 해당 단지의 집 개수를 반환한다.

 

3. BFS 호출 후 반환받은 값을 벡터에 넣어준다.

 

4. 벡터를 오름차순 정렬한다.

 

5. 벡터 원소의 개수와 정렬된 원소를 각 줄에 한 개씩 출력한다.

 

 

코드

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

struct State
{
   int x, y;
};

int dx[] = {1, -1, 0,0};
int dy[] = {0,0,1,-1};
int n, ans;
int house[25][25];
bool visited[25][25];
vector<int> num;

int bfs(int x, int y){

    // 큐 생성
    queue<State> q;

    // 시작 집 방문 표시
    visited[x][y] = true;

    // 시작 집을 q에 삽입
    q.push({x,y});
    ans = 1;

    State cur;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            // 범위 체크
            if(nx <0 || nx >=n || ny<0 || ny>=n) continue;

            // 아직 방문하지 않은 집인 경우 
            if(visited[nx][ny] != true && house[nx][ny]==1){
                
                // 방문 처리
                visited[nx][ny]= true;

                // 찾은 집의 개수 증가시키고 삽입
                q.push({nx,ny});
                ans ++;
            }
        }
    }
    return ans;
}

int main(){

    // 입력받기
    cin >> n;
    
    for(int i=0; i<n; i++){
        string row;
        cin >> row; // 한 줄을 문자열로 받기

        for(int j = 0; j < n; j++) {
            house[i][j] = row[j] - '0'; // 문자 -> 숫자로 변환
        }
    }

    // 단지 탐색
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 새로운 아직 탐색하지 않은 주택을 발견한 경우,
            if(house[i][j]==1 && visited[i][j]!=true){
                num.push_back(bfs(i,j));
            }
        }
    }

    // 오름차순 정렬
    sort(num.begin(), num.end());
    
    cout << num.size() << "\n";

    // 출력
    for(int i=0; i<num.size(); i++){
        cout << num[i] << "\n";
    }

    return 0;
}