JArchive 프로그래밍 일기

문제

섬의개수 백준 4963번

리뷰

미로 탐색 문제와 비슷했다.

지도에서 땅은 1이고 바다는 0으로 표기되어 있다. 여기서 섬의 개수를 구한다.

이중 for문으로 모든 지점에서 BFS를 시작한다. 땅을 발견할 경우에만 BFS를 시작한다.

핵심은 땅을 발견했을 때, 그 인접한 (가로,세로,대각선) 땅은 전부 바다로 바꾸고 ( 탐색하며 발견한 1은 0으로. ) 끝내는 것이다.

그 지점의 BFS가 종료되면 섬 개수를 하나 센다. cnt + 1

설계 하고 코딩하고 디버깅 하는데 1시간 정도 걸렸다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 50
using namespace std;

int M[M_MAX+1][M_MAX+1]; //지도  
int w, h; // 너비, 높이  

// 8방향 
int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 지도 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < h && j >= 0 && j < w) ? 1:0;
} 

void BFS(int x, int y){  // 시작점 땅 기준으로 근처 땅을 전부 바다로 만든다. 

    queue<pair<int,int>> q;

    q.push({x, y}); // 시작점 푸시  
    M[x][y] = 0; // 방문 표시  

    while(!q.empty()){ // 1 땅  0바다 

        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++){ // 8방향 검사  

            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];

            if(boundary(next_x, next_y) ){ // 범위 내부이면  

                if(M[next_x][next_y] == 1){ // 땅이라면 

                    q.push({next_x, next_y}); // 방문한 좌표 큐에 넣기  
                    M[next_x][next_y] = 0; // 바다로 만든다  
                }
            }
        }
    }

}

int main(void){

    while(1){

        // w, h  (열, 행)
        cin >> w >> h;

        if(w==0 && h==0) break;

        // 지도 입력받기  
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> M[i][j];
            }
        } 

        int cnt = 0; // 섬의 개수  

        for(int i = 0; i < h; i++){  // 시작점 탐색 ( 땅 찾기 )
            for(int j = 0; j < w; j++){

                if(M[i][j] == 1){ // 땅 발견  
                    BFS(i, j); 
                    cnt++;
                } 

             }
        } 
        cout << cnt << '\n';    

        memset(M, 0, sizeof(M)); // M배열 초기화
    }

    return 0;    
}