M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 4963 - 섬의 개수

1 분 소요

문제

백준 4983번 - 섬의 개수 문제 풀러가기

문제 분석

  • 이 문제는 백준 2667 - 단지 번호 붙이기 와 유사한 문제다.
  • 차이점은 2667번은 대각선으로 연결되어 있는 경우는 포함하지 않았지만, 여기서는 대각선으로 연결되어 있으면 하나로 같이 묶는다는 것이다.

문제 풀이 코드(c++)

  1. 전체 코드

    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
    #include <cstdio>
    #include <queue>
    #include <cstring>
     
    using namespace std;
     
    pair<int, int> map[50][50];
     
    int island=0;
     
    queue<pair<int, int>> q;
     
    int w, h;
     
    int dx[] = { 1,1,1,0,0,-1,-1,-1 };
    int dy[] = { 0,1,-1,1,-1,0,1,-1 };
     
    void bfs(int i, int j) {
        q.push(make_pair(i, j));
        map[i][j].second = island;
     
        while (!q.empty()) {
            int currentRow = q.front().first;
            int currentColumn = q.front().second;
     
            for (int k = 0; k < 8; k++) {
                int nextRow = currentRow + dy[k];
                int nextColumn = currentColumn + dx[k];
                if ((0 <= nextRow) && (nextRow < h) && (0 <= nextColumn && nextColumn < w)) {
                    if (map[nextRow][nextColumn].first == 1 && map[nextRow][nextColumn].second == 0) {
                        map[nextRow][nextColumn].second = island;
                        q.push(make_pair(nextRow, nextColumn));
                    }
                }
            }
     
            q.pop();
        }
        
     
    }
     
    int main() {
        
        
        while (1) {
            scanf("%d %d", &w, &h);
     
            if (w == 0 && h == 0) {
                break;
            }
     
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    scanf("%d ", &map[i][j].first);
                }
            }
     
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j].first == 1 && map[i][j].second == 0) {
                        island++;
                        bfs(i, j);
                    }    
                }
            }
     
            printf("%d\n", island);
     
            island = 0;
            memset(map, 0, sizeof(map));
        }
        
        return 0;
    }
    		cs
    • 15~16번째 : 상하좌우대각선을 쉽게 확인 하기 위한 배열이다.
      • (1,1)을 원래 행과 열에 더해주면 : 오른쪽 아래 대각선
      • (-1,0)을 원래 행과 열에 더해주면 : 상
      • (0,1)을 원래 행과 열에 더해주면 : 우
      • (-1,1)을 원래 행과 열에 더해주면 : 오른쪽 위 대각선

  2. bfs 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void bfs(int i, int j) {
        q.push(make_pair(i, j));
        map[i][j].second = island;
        while (!q.empty()) {
            int currentRow = q.front().first;
            int currentColumn = q.front().second;
            for (int k = 0; k < 8; k++) {
                int nextRow = currentRow + dy[k];
                int nextColumn = currentColumn + dx[k];
                if ((0 <= nextRow) && (nextRow < h) && (0 <= nextColumn && nextColumn < w)) {
                    if (map[nextRow][nextColumn].first == 1 && map[nextRow][nextColumn].second == 0) {
                        map[nextRow][nextColumn].second = island;
                        q.push(make_pair(nextRow, nextColumn));
                    }
                }
            }
            q.pop();
        }
        
    }
    		cs
    • 일반적인 문제의 bfs 함수와 달리, 이곳에서는 큐에 행과 열의 값을 넣어줘야 하기 때문에 큐에 행과 열의 쌍으로 이루어진 pair 값을 넣어준다.
      • 7~16번째 반복문 : 이 문제는 위, 아래, 오른쪽, 왼쪽, 대각선의 값만 확인하면 되기 때문에 dx 배열과 dy 배열의 값을 이용하여 8번의 반복문을 통해 확인.
        • 이동 할 때, 지도의 밖을 벗어나면 안되므로 10번째 줄과 같은 조건문을 사용했습니다.
      • 14번째 줄 : map[다음 행] [다음 열]의 첫번째 값이 1이고, 두번째 값이 0이면 연결 되어 있고, 아직 방문하지 않았다는 것이다.
        • 그러므로 방문하여 map[다음 행] [다음 열]의 두번째 값에 현재 섬 번호를 넣어주고 큐에 현재 위치 쌍을 넣어준다.

  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
    30
    31
    32
    33
    int main() {
        
        
        while (1) {
            scanf("%d %d", &w, &h);
     
            if (w == 0 && h == 0) {
                break;
            }
     
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    scanf("%d ", &map[i][j].first);
                }
            }
     
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j].first == 1 && map[i][j].second == 0) {
                        island++;
                        bfs(i, j);
                    }    
                }
            }
     
            printf("%d\n", island);
     
            island = 0;
            memset(map, 0, sizeof(map));
        }
        
        return 0;
    }
    		cs
    • 4번째 줄 : 문제에 w와 h에 모두 0, 0이 입력 됬을 때 중단한다고 했으므로 무한 루프가 돌 수 있도록 항상 true가 되는 조건인 1을 while문의 조건으로 넣어줬다.
      • 7~9번째 줄 : w와 h가 모두 0,0 일때 중단되어야 하므로, break를 넣어줬다.
    주의 할 점 - h는 행 관련, w는 열 관련이라는 것이다.
    본인은 처음에 문제에서 w와 h 순으로 입력을 받으니까 지도 값을 받는 for문에서도 w, h 순으로 돌리는 실수를 범하기도 했다.

  4. 추가 : dfs로 작성한다면(재귀함수로)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void dfs(int i, int j) {
        map[i][j].second = island;
     
        for (int k = 0; k < 8; k++) {
            int nextRow = i + dy[k];
            int nextColumn = j + dx[k];
            if ((0 <= nextRow) && (nextRow < h) && (0 <= nextColumn && nextColumn < w)) {
                if (map[nextRow][nextColumn].first == 1 && map[nextRow][nextColumn].second == 0) {
                    dfs(nextRow, nextColumn);
                }
            }
        }
    }
    		cs





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

댓글남기기

참고