[백준/c++] 4963번: 섬의 개수

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

4963번: 섬의 개수

 

문제 요약

 

가로, 세로, 대각선으로 연결된 사각형 = 섬

섬의 개수를 세는 프로그램을 작성해라.

 

 

범위

 

지도의 너비 w와 높이 h (50보다 작거나 같은 양의 정수)

 

 

---

 

 

상하좌우, 대각선까지 포함해야 하므로 방향을 담은 배열dir을 확장시켰다.

배열의 x, y 좌표를 나타내는 것이 반대이므로 처음에 입력받을 때부터 반대로 입력해서 헷갈리지 않도록 해줬다.

 

 

#include <iostream>
using namespace std;
int w, h;
int map[52][52], dir[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {-1, 1}};
bool visited[52][52];

void input(){
    for(int i=0; i<w; i++) for(int j=0; j<h; j++) {map[i][j] = 0; visited[i][j] = false;} //initialize
    for(int i=0; i<w; i++) for(int j=0; j<h; j++) cin >> map[i][j];
}

void dfs(int x, int y){
    visited[x][y] = true;
    for(int i=0; i<8; i++){
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        if(dx < 0 || dy < 0 || dx >= w || dy >= h) continue;
        if(map[dx][dy] == 0) continue;
        if(visited[dx][dy]) continue;
        dfs(dx, dy);
    }
}

void solution(){
    int cnt = 0;
    for(int i=0; i<w; i++){
        for(int j=0; j<h; j++){
            if(!visited[i][j] && map[i][j] == 1){
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while(true){
        cin >> h >> w;
        if(w == 0 && h == 0) break;
        input();
        solution();
    }
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!