백준 4963번 섬의 개수 - C++(cpp) 풀이

---

 

1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다.
2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다.
3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다.

 

1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다.

 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 땅인 칸을 정점으로, 이어져있는 땅들을 간선으로 이으면 그래프가 된다.

 

2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다.

 이제 섬은 그래프의 연결 요소와 같다는 것을 알 수 있다.

 

3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다.

 따라서 섬의 개수는 곧 그래프의 연결 요소 개수와 같다. 한 번의 DFS/BFS로 하나의 연결 요소에 속하는 모든 정점을 방문할 수 있으므로, 모든 정점을 방문하기까지 DFS/BFS의 호출 횟수가 곧 연결 요소의 개수와 같다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

int W, H;
bool board[51][51], visit[51][51];
int dr[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dc[] = {0, 0, -1, 1, -1, 1, -1, 1};

void DFS(int r, int c) {
    visit[r][c] = true;
    
    for (int i=0; i<8; i++) {
        int next_r = r + dr[i];
        int next_c = c + dc[i];
        
        if (0 > next_r || next_r >= H || 0 > next_c || next_c >= W) continue;
        if (visit[next_r][next_c] || !board[next_r][next_c]) continue;
        
        DFS(next_r, next_c);
    }
}

int solution() {
    int ret = 0;
    
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            if (visit[i][j] || !board[i][j]) continue;
            DFS(i, j);
            ret++;
        }
    }
    
    return ret;
}

void init_testcase() {
    memset(visit, 0, sizeof(visit));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    while (true) {
        init_testcase();
        
        cin >> W >> H;
        if (W == 0 && H == 0) break;

        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                cin >> board[i][j];
            }
        }
        
        cout << solution() << "\n";
    }

    return 0;
}