섬의 개수

4963번 : 섬의 개수
https://www.acmicpc.net/problem/4963

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입출력

// 입력				//출력
1 1   				0
0					1
2 2					1
0 1					3
1 0					1
3 2					9
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

해결 방향

땅과 바다를 true와 false로 구분한 다음, 땅에 대해서만 깊이 우선 탐색을 한다. 대각선을 포함하여, 땅과 인접한 8개의 영역을 고려해야 한다.

코드

#include <iostream>
using namespace std;

bool v[50][50];

void dfs(int x, int y) {
    // 현재 방문 중인 땅을 체크한다. 
    v[x][y] = false;
    
    /* 위, 아래, 왼쪽, 오른쪽, 대각선에 땅이 있다면 함수를 재귀호출한다.
   	   단, 인덱스 범위를 초과하지 않도록 조건문을 추가한다. */
    if(x!=49 && y!=49) if(v[x+1][y+1]) dfs(x+1, y+1);
    if(x!=0 && y!=0) if(v[x-1][y-1]) dfs(x-1, y-1);
    if(x!=49 && y!=0) if(v[x+1][y-1]) dfs(x+1, y-1);
    if(x!=0 && y!=49) if(v[x-1][y+1]) dfs(x-1, y+1);
    if(x!=49) if(v[x+1][y]) dfs(x+1, y);
    if(x!=0) if(v[x-1][y]) dfs(x-1, y);
    if(y!=49) if(v[x][y+1]) dfs(x, y+1);
    if(y!=0) if(v[x][y-1]) dfs(x, y-1);
}

int main() {
    int w, h, cnt;
    while(1) {
        cnt = 0;
        cin >> w >> h;
        if(w==0 && h==0) break;
		
        // 땅은 1(true), 바다는 0(false) 이차원 배열로 저장한다.
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                cin >> v[i][j];
            }
        }
        
        // 땅 이라면 카운트하고 DFS함수를 호출한다.
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                if(v[i][j]) {
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        
        // 섬의 개수를 출력한다.
        cout << cnt << '\n';
    }
    
    return 0;
}

메모리 : 2056KB
시간 : 4ms