M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 2667 - 단지 번호 붙이기

1 분 소요

백준 2667 - 단지 번호 붙이기 풀러가기

문제 풀이

이 문제는 플러드 필 이라는 알고리즘을 이용하면 됩니다.

0과 1로 이루어진 배열이 있고, 위의 그림처럼 1이 연결되어 있는 곳을 한 단지라고 합니다.

1이 연결되어 있는 곳이 한 단지…?

무언가 생각나는 게 있으신가요? 바로 연결 요소 인데요. (연결 요소에 대한 설명이 필요하다면)

연결 요소 를 구하듯이 문제를 풀면되는구나! 생각하시면 되겠습니다.

그리고 이 문제에서 정점과 간선을 표현하기 위해 인접 행렬과 리스트 중에 뭘 써야 하나 고민이 될 수 있는데, 지도 정보를 배열에 저장하면 현재 위치에서 위, 아래, 왼쪽, 오른쪽만 확인 해주면 되기 때문에 따로 자료구조를 만들어 줄 필요가 없습니다!

  1. 전체 코드(C++)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <cstdio>
     
    using namespace std;
     
    int n;
     
    //지도 정보 저장
    pair<int, int> house[25][25];
     
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
     
    int comp=0;
    vector<int> compCount;
     
    queue<pair<int, int>> q;
     
    void bfs(int i, int j) {
        int count=1;
        house[i][j].second = comp;
        q.push(make_pair(i, j));
     
        while (!q.empty()) {
            int currentRow = q.front().first;
            int currentColumn = q.front().second;
     
            for (int k = 0; k < 4; k++) {
                int nextRow = currentRow + dy[k];
                int nextColumn = currentColumn + dx[k];
                if ((0 <= nextRow && nextRow < n) && (0 <= nextColumn && nextColumn < n)) {
                    if (house[nextRow][nextColumn].first == 1 && house[nextRow][nextColumn].second == 0) {
                            house[nextRow][nextColumn].second = comp;
                            count++;
                            q.push(make_pair(nextRow, nextColumn));
                    }
                }
                    
            }
            q.pop();
        }
     
        compCount.push_back(count);
    }
     
    int main() {
     
        scanf("%d", &n);
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%1d", &house[i][j].first);
            }
        }
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (house[i][j].first == 1 && house[i][j].second == 0) {
                    comp++;
                    bfs(i, j);
                }
            }
        }
     
        printf("%d\n", comp);
     
        sort(compCount.begin(), compCount.end());
     
        for (auto x : compCount) {
            printf("%d\n", x);
        }
     
        return 0;
    }
    		cs
    • 11번째 줄 : 지도 정보를 pair를 통해 저장하고 있습니다.
      • pair의 첫번째 요소 : 지도 정보(0과 1)
      • pair의 두번째 요소 : 단지 정보
    • 13~14번째 줄 : 방향 정보를 담고 있다.(bfs 부분에서 설명)

  2. bfs 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void bfs(int i, int j) {
        int count=1;
        house[i][j].second = comp;
        q.push(make_pair(i, j));
     
        while (!q.empty()) {
            int currentRow = q.front().first;
            int currentColumn = q.front().second;
     
            for (int k = 0; k < 4; k++) {
                int nextRow = currentRow + dy[k];
                int nextColumn = currentColumn + dx[k];
                if ((0 <= nextRow && nextRow < n) && (0 <= nextColumn && nextColumn < n)) {
                    if (house[nextRow][nextColumn].first == 1 && house[nextRow][nextColumn].second == 0) {
                            house[nextRow][nextColumn].second = comp;
                            count++;
                            q.push(make_pair(nextRow, nextColumn));
                    }
                }
                    
            }
            q.pop();
        }
     
        compCount.push_back(count);
    }
    		cs
    • 이전의 다른 문제의 bfs 함수와 달리, 이곳에서는 큐에 행과 열의 값을 넣어줘야 하기 때문에 큐에 행과 열의 쌍으로 이루어진 pair 값을 넣어줍니다.
    • 10~21번째 반복문 : 이 문제는 위, 아래, 오른쪽, 왼쪽의 값만 확인하면 되기 때문에 dx 배열과 dy 배열의 값을 이용하여 4번의 반복문을 통해 확인하고 있습니다.
      • (1,0) => 위의 행으로 이동
      • (-1,0)=> 아래 행으로 이동
      • (0,1) => 오른쪽 열로 이동
      • (1,0) => 왼쪽 열로 이동
      • 이동 할 때, 지도의 밖을 벗어나면 안되므로 13번째 줄과 같은 조건문을 사용했습니다.
    • 14번째 줄 : house[다음 행] [다음 열]의 첫번째 값이 1이고, 두번째 값이 0이면 연결 되어 있고, 아직 방문하지 않았다는 것입니다.
      • 그러므로 방문하여 house[다음 행] [다음 열]의 두번째 값에 현재 단지 번호를 넣어주고 큐에 현재 위치 쌍을 넣어줍니다.
    • 25번째 줄 : 방문 가능한 모든 탐색이 끝났다면, compCount라는 배열에 현재 단지에 속하는 집의 숫자를 넣어줍니다.

  3. main 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int main() {
     
        scanf("%d", &n);
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%1d", &house[i][j].first);
            }
        }
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (house[i][j].first == 1 && house[i][j].second == 0) {
                    comp++;
                    bfs(i, j);
                }
            }
        }
     
        printf("%d\n", comp);
     
        sort(compCount.begin(), compCount.end());
     
        for (auto x : compCount) {
            printf("%d\n", x);
        }
     
        return 0;
    }
    		cs
    • 7번째 줄 : 예제를 통해 지도를 입력 받을 때 10011 이런식으로 숫자들이 붙어서 입력되는 것을 알 수 있습니다. 따라서, 1자리씩 끊어서 입력 받는다는 뜻으로 %1d 로 작성해줬습니다.
    • 13번째 줄 : house[행] [열]의 첫번째 값이 1이고 두번째 값이 0이면, 건물은 있지만 아직 방문을 하지 않은 곳 입니다. 따라서 해당 위치부터 방문을 시작하기 위해 bfs 함수를 호출해주고, 새로운 단지의 시작이므로 comp의 값을 증가시켜 줍니다.
    • 22번째 줄 : 문제에서 단지에 속하는 집의 수를 오름차순으로 출력하라고 했으니 단지에 속하는 집의 수의 정보를 가진 compCount를 sort 시킵니다. 참고로 저는 문제 대충 읽고, 처음에 sort 시키지 않고 출력하는 코드를 작성했더니 계속 ‘틀렸습니다’가 나와서 고생했습니다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고