[백준 4963 - C/C++] 섬의 개수: DFS/BFS

www.acmicpc.net/problem/4963

4963번: 섬의 개수

문제

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

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

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

 

입력

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

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

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

 

출력

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

 

풀이

기존에 C언어로 BFS알고리즘으로 풀었던 문제를 이번엔 C++로 DFS를 이용하여 풀이하였습니다.

 

c언어 BFS풀이 : excited-hyun.tistory.com/12

[백준 4963 - C언어] 섬의 개수: BFS

 

가로, 세로, 대각선을 모두 고려해야하므로 8가지 방향으로 이동하면서 이어진 섬을 찾아야한다.

2중 for문에서 모든 map을 지나며 방문 여부와 땅인지 여부를 확인하여 dfs함수를 호출해 이어진 땅들을 모두 방문한다.

dfs함수의 재귀가 모두 끝나 다시 main으로 돌아올때가 하나의 섬을 찾은 것이므로, 그때마다 섬의 개수를 하나씩 증가시킨다.

 

또한 이문제는 입력이 한번 들어오는게 아니라 0 0이 입력될 때 까지 계속 들어오기 때문에 visited배열을 반드시 초기화해주어야 한다!!

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int map[51][51];
int visited[51][51];

int C[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int R[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int cnt;

void dfs(int n, int m, int now_r, int now_c);

int main (void){
    int h, w;
    
    while(1){
        scanf("%d %d", &w, &h);
        if(h==0 && w==0)
            break;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                scanf("%d", &map[i][j]);
            }
        }
        
        cnt = 0;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(visited[i][j] ==0 && map[i][j] == 1){
                    dfs(h, w, i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                visited[i][j] = 0;
            }
        }

    }
}

void dfs(int n, int m, int now_r, int now_c){
    int next_r, next_c;
    
    visited[now_r][now_c] = 1;
    
    for(int i=0; i<8; i++){
        next_r = now_r + R[i];
        next_c = now_c + C[i];
        if(next_r <0 || next_r >=n || next_c <0 || next_c >= m)
            continue;
        if(map[next_r][next_c]==0)
            continue;
        if(visited[next_r][next_c] == 1)
            continue;
        dfs(n, m, next_r, next_c);
    }
}