JArchive 프로그래밍 일기

문제

단지 번호 붙이기 백준 2667번

리뷰

오늘의 교훈. 문제를 정독하자. 조급해지면 지는건데...

마지막에 단지 마다의 집 개수를 sort 해서 출력하라는 것을 빼먹고 왜틀렸나 헤맸다 ㅠㅠ

그리고 처음에 시작점을 큐에 푸시할 때도 A와 D 배열을 갱신해줘야 한다.
A에는 방문했으니까 0, D에는 단지 숫자를 써줘야 한다.

배열 A는 주어진 배열이고,

배열 D는 단지를 채운 결과를 저장할 배열이다.

main 함수에서는 배열 A를 순회해서 1을 만나면 BFS 탐색을 시작한다.

BFS는 A배열이 1이고, D배열이 0 인 경우에 house 개수를 센다. 단지의 집이 몇개인지 세는것이다.

if(in_boundary(xx, yy)){

     if(A[xx][yy] == 1 && D[xx][yy] == 0){
         A[xx][yy] = 0; // 방문표시  
         D[xx][yy] = danzi; // 단지표시 
         q.push({xx, yy});
         house_num++;
     }
}

A배열에서 방문한 곳은 다시 방문 안하도록 0 으로 변경한다.

D배열에는 단지 번호를 써준다.

BFS가 끝나면 house 개수를 리턴한다.

상하좌우가 A배열 인덱스 범위 안에 있는지는 in_boundary함수를 이용해서 true/false 확인해줬다.

int dx[5] = {-1, 1, 0, 0}; // 상하좌우 
int dy[5] = {0, 0, -1, 1};  

bool in_boundary(int x, int y){
    return (x >= 0 && x < N && y >= 0 && y < N) ? 1:0;
}

마지막에 단지의 집 개수를 오름차순으로 정렬하여 출력한다.

    // 답 출력  
    cout << danzi << '\n'; // 단지의 총 개수 

    sort(house.begin(), house.end());  // 오름차순 정렬해서 출력 !

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

코드

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

int N;
int A[27][27]; 
int D[27][27];

int dx[5] = {-1, 1, 0, 0}; // 상하좌우 
int dy[5] = {0, 0, -1, 1};  

 // 단지번호붙이기  2667 

bool in_boundary(int x, int y){
    return (x >= 0 && x < N && y >= 0 && y < N) ? 1:0;
}

int BFS(int i, int j, int danzi){

    queue<pair<int,int> > q;
    int house_num = 1;

    q.push({i, j});
    A[i][j] = 0;
    D[i][j] = danzi;

    while(!q.empty()){

        pair<int,int> now = q.front();
        int x = now.first;
        int y = now.second;
        q.pop();

        for(int i = 0; i < 4; i++ ){ // 상하좌우 탐색 
             int xx = x + dx[i];
             int yy = y + dy[i];

             if(in_boundary(xx, yy)){

                 if(A[xx][yy] == 1 && D[xx][yy] == 0){
                     A[xx][yy] = 0; // 방문표시  
                     D[xx][yy] = danzi; // 단지표시 
                     q.push({xx, yy});
                     house_num++;
                }
            }
        }
    }

    return house_num;
} 

int main(void){

    cin >> N;

    int danzi = 0;
    vector<int> house;

    for(int i = 0; i < N; i++){

        string st; 
        cin >> st;

        for(int j = 0; j < N; j++){
            A[i][j] = st[j] - 48;
        }
    } // 입력받기 끝  

    // 탐색 시작  
     for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(A[i][j] == 1) {
                int house_num = BFS(i, j, ++danzi); 
                house.push_back(house_num);
            }
        }
    }

    // 답 출력  
    cout << danzi << '\n';

    sort(house.begin(), house.end());  // 오름차순 정렬해서 출력 !!

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

    return 0;    
}