2667번 - 단지번호붙이기

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

2667번 - 단지번호붙이기

문제 요약:

  (1) 정사각형 모양의 지도를 제공(N²의 배열, 5 <= N <= 25)

     => 0은 비어있는 곳, 1은 집이 존재

  (2) 이웃들을 묶어서 단지를 형성

     => 특정한 집을 기준으로 동서남북 중 한 곳이라도 붙어 있어야 같은 단지로 인정

     => 대각선으로 붙어있는 집은 같은 단지가 아님

  (3) 각 단지의 집의 수를 오름차순으로 출력

 

문제 해결:

   A. 지도를 저장하는 배열, 방문 여부를 저장하는 배열 설정

   B. 배열의 (0, 0)부터 (N-1, N-1)으로 반복하여 해당하는 곳에 집이 있는 지 확인후 해당 집을 기준으로 BFS를 수행

   C. BFS가 끝나는 순간에 해당 단지의 수를 저장

   D. 저장된 총 단지수를 출력하고 각 단지내의 집의 수를 오름차순으로 출력

 

미리 공부할 내용:

  => 해당 내용을 이해하기 앞 서 BFS의 개념을 알아야 한다.

  => 아래의 사이트에 가서 개념을 익히고 오자.

trying-ce-student.tistory.com/18

1260번 - DFS와 BFS

알고리즘:

 

   A. 지도를 저장하는 배열, 방문 여부를 저장하는 배열 설정

    1. N의 최대값이 25이므로, 해당 값을 상수(MAP_SIZE)로 설정

    2. 변수와 함수관리를 편하게 하기 위해 클래스로 설정하였다.

    3. 지도를 저장하는 배열(squ_map), 방문 여부를 저장하는 배열(check_map), 각 단지 집의수를 저장하는 배열(apart)

 

#define MAP_SIZE 25
 
class BFS {
private:
    int squ_map[MAP_SIZE][MAP_SIZE];
    int check_map[MAP_SIZE][MAP_SIZE];
    std::vector<int> apart;
public:
    BFS();
    void InputVal(int (*inp_map)[MAP_SIZE], int n);
    void Search(int start_x, int start_y, int n);
    int IsVisit(int x, int y);
    void PrintAnswer();
};

// BFS 클래스 탐색 함수
void BFS::Search(int start_row, int start_col, int n) {
    int apart_size = 0;
    std::queue<std::pair<int, int>> q;
    q.push(std::make_pair(start_row, start_col));
    
 
    while (!q.empty()) {
        std::pair<int, int> cur = q.front();
        apart_size++;
        q.pop();
        check_map[cur.first][cur.second] = 1;
 
        for (int i = 0; i < 4; i++) {
            int next_row = cur.first + directX[i];
            int next_col = cur.second + directY[i];
 
            // 배열 밖으로 나가는 경우
            if (next_row < 0 || next_row >= n || next_col < 0 || next_col >= n) {
                continue;
            }
 
            if ((check_map[next_row][next_col] != 1) && (squ_map[next_row][next_col] == 1)) {
                q.push(std::make_pair(next_row, next_col));
                check_map[next_row][next_col] = 1;
            }
        }
    }
    apart.push_back(apart_size);
}
 
 
int main() {
 
    // 변수
    int n;
    int arr[MAP_SIZE][MAP_SIZE];
    BFS bfs;
 
    // 변수 입력
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 띄어쓰기 없이 입력받았을 때, 하나씩 입력 받기
            scanf("%1d", &arr[i][j]);
        }
    }
 
    // 입력 받은 값 bfs에 대입
    bfs.InputVal(arr, n);
    // 단지를 구하고 각 단지 집의 수 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // (i, j)에 집이 존재하고 방문하지 않은 경우
            if (arr[i][j] == 1 && bfs.IsVisit(i, j) == 0) {
                bfs.Search(i, j, n);
            }
        }
    }
 
    // 결과 출력
    bfs.PrintAnswer();
 
    return 0;
}

       1. 각 단지내의 집의 수를 오름차순으로 정렬

       2. 총 단지수를 출력

       3. 각 단지내의 집의 수를 출력

// 정답 출력
void BFS::PrintAnswer() {
    std::sort(apart.begin(), apart.end());
    printf("%d\n", apart.size());
    for (auto apart_val : apart) {
        printf("%d\n", apart_val);
    }
}

소스 코드(전체적인 코드):

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
#define MAP_SIZE 25
 
// east, west, south, north;
int directX[] = { 1, -1, 0, 0 };
int directY[] = { 0, 0, -1, 1 };
 
class BFS {
private:
    int squ_map[MAP_SIZE][MAP_SIZE];
    int check_map[MAP_SIZE][MAP_SIZE];
    std::vector<int> apart;
public:
    BFS();
    void InputVal(int (*inp_map)[MAP_SIZE], int n);
    void Search(int start_x, int start_y, int n);
    int IsVisit(int x, int y);
    void PrintAnswer();
};
 
// BFS 클래스 생성자
BFS::BFS() {
    for (int i = 0; i < MAP_SIZE; i++) {
        for (int j = 0; j < MAP_SIZE; j++) {
            squ_map[i][j] = 0;
            check_map[i][j] = 0;
        }
    }
}
 
// BFS 클래스 값 대입
void BFS::InputVal(int(*inp_map)[MAP_SIZE], int n){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            squ_map[i][j] = inp_map[i][j];
        }
    }
}
 
// BFS 클래스 탐색 함수
void BFS::Search(int start_row, int start_col, int n) {
    int apart_size = 0;
    std::queue<std::pair<int, int>> q;
    q.push(std::make_pair(start_row, start_col));
    
 
    while (!q.empty()) {
        std::pair<int, int> cur = q.front();
        apart_size++;
        q.pop();
        check_map[cur.first][cur.second] = 1;
 
        for (int i = 0; i < 4; i++) {
            int next_row = cur.first + directX[i];
            int next_col = cur.second + directY[i];
 
            // 배열 밖으로 나가는 경우
            if (next_row < 0 || next_row >= n || next_col < 0 || next_col >= n) {
                continue;
            }
 
            if ((check_map[next_row][next_col] != 1) && (squ_map[next_row][next_col] == 1)) {
                q.push(std::make_pair(next_row, next_col));
                check_map[next_row][next_col] = 1;
            }
        }
    }
    apart.push_back(apart_size);
}
 
// 해당 위치에 방문 여부 리턴
int BFS::IsVisit(int x, int y) {
    return check_map[x][y];
}
 
 
// 정답 출력
void BFS::PrintAnswer() {
    std::sort(apart.begin(), apart.end());
    printf("%d\n", apart.size());
    for (auto apart_val : apart) {
        printf("%d\n", apart_val);
    }
}
 
int main() {
 
    // 변수
    int n;
    int arr[MAP_SIZE][MAP_SIZE];
    BFS bfs;
 
    // 변수 입력
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 띄어쓰기 없이 입력받았을 때, 하나씩 입력 받기
            scanf("%1d", &arr[i][j]);
        }
    }
 
    // 입력 받은 값 bfs에 대입
    bfs.InputVal(arr, n);
    // 단지를 구하고 각 단지 집의 수 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // (i, j)에 집이 존재하고 방문하지 않은 경우
            if (arr[i][j] == 1 && bfs.IsVisit(i, j) == 0) {
                bfs.Search(i, j, n);
            }
        }
    }
 
    // 결과 출력
    bfs.PrintAnswer();
 
    return 0;
}
 
 

 

한줄평:

 -> 탐색을 하는 것이 트리처럼 2가지 종류만 있는 것이 아니다.