[BOJ] 4963. 섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

단순 연결 요소 문제로 모든 정점을 탐색하는 bfs나 dfs를 사용하여 풀 수 있다.

이 문제는 대각선도 연결되어 있으므로 방향을 상, 하, 좌, 우에다가 대각선 네 방향까지 모두 탐색해주면 된다.

섬의 개수만 세면 되므로 bfs가 매번 실행될 때마다 ans값이 증가하도록 구현했다.

 

테스트 케이스의 개수가 명시되어 있지 않으므로 while문에서 w와 h값이 모두 0인 경우에 break 하도록 해주었다.

ans는 각 테스트 케이스가 끝날 때마다 출력해준다.

 

주의할 점은 ans는 while문 안에서 선언해주거나 아니면 다시 0으로 초기화되도록 해주어야 한다.

check 배열 역시 새로운 테스트 케이스에서 지도의 정보를 입력받을 때 같이 false로 초기화해준다.

 

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
int h,w;
int map[50][50];
bool check[50][50];
int dx[] = {0,0,1,-1,-1,-1,1,1};
int dy[] = {1,-1,0,0,-1,1,-1,1};
 
void bfs(int x, int y) {
    queue<pair<int,int> > q;
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        //8가지 방향으로 이동
        for(int k=0; k<8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
 
            //땅이고, 방문하지 않았으면 방문
            if(map[nx][ny] == 1 && check[nx][ny] == false) {
                q.push(make_pair(nx,ny));
                check[nx][ny] = true;
            }
        }
    }
}
 
int main() {
    
 
    while(true) {
        int ans = 0;
        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]);
                check[i][j] = false;
            }
        }
 
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
 
                //땅이고 아직 방문하지 않았다.
                if(map[i][j] == 1 && check[i][j] == false) {
                    ans++;
                    bfs(i,j);
                }
            }
        }
 
       printf("%d\n", ans);
    }
    return 0;
}