백준[4963] - 섬의 개수

문제

백준 4963 문제 보기

접근 방법

동서남북과 대각선 방향을 맵의 유효 범위안에서 완전 탐색하면 답을 출력할 수 있다.

코드

#include <iostream>
#include <cstring>
 
using namespace std;
 
int h, w;
int map[50][50];
int visited[50][50];
// 동 북 남 서
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
// 대각선 방향
int dx2[4] = {1, 1, -1, -1};
int dy2[4] = {1, -1, -1, 1};
 
int dfs(int i, int j) {
 
    visited[i][j] = 1;
 
    for(int k = 0; k < 4; k ++) {
        // 지도 범위 체크
        if(j + dx[k] >= 0 && j + dx[k] < w && i + dy[k] >= 0 && i + dy[k] < h) {
            // 땅이면서 방문하지 않았는지 체크
            if(map[i + dy[k]][j + dx[k]] && !visited[i + dy[k]][j + dx[k]])
                dfs(i + dy[k], j + dx[k]);
        }
    }
 
    for(int k = 0; k < 4; k ++) {
        if(j + dx2[k] >= 0 && j + dx2[k] < w && i + dy2[k] >= 0 && i + dy2[k] < h) {
            if(map[i + dy2[k]][j + dx2[k]] && !visited[i + dy2[k]][j + dx2[k]])
                dfs(i + dy2[k], j + dx2[k]);
        }
    }
 
    return 0;
}
 
int main() {
 
    while(1) {
 
        cin >> w >> h;
 
        if(w == 0 && h == 0)
            break;
 
        memset(map, 0, sizeof(map));
        memset(visited, 0, sizeof(visited));
 
        for(int i = 0; i < h; i ++) {
            for(int j = 0; j < w; j ++) {
                cin >> map[i][j];
            }
        }
 
        int cnt = 0;
        for(int i = 0; i < h; i ++) {
            for(int j = 0; j < w; j ++) {
                if(map[i][j] && !visited[i][j]) {
                    cnt ++;
                    dfs(i, j);
                }
            }
        }
 
        cout << cnt << '\n';
    }
 
    return 0;
}