[백준 4963, c++] 섬의 개수(bfs,dfs)

문제 번호

• 4963(https://www.acmicpc.net/problem/4963)

문제 및 입/출력

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

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

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

 

입력

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

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

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

 

출력

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

 

예제 입력1

1 1 0 2 2 0 1 1 0 3 2 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

예제 출력1

0 1 1 3 1 9

 

문제 풀이

이 문제는 2667 단지번호붙이기와 거의 유사한 문제이다. 그렇기에 더 쉽게 접근할 수 있었다. 

역시 이 문제도 bfs와 dfs 둘 다 적용해서 진행하였다.

 

소스코드 상에 주석으로 자세한 설명을 적어놓았지만, 다시한번 설명하겠다.

 

0. 높이(h)와 너비(w) 값을 입력 받는다. (0, 0 이라면 프로그램 종료)

1. 우선 배열을 통해 그래프 정보를 입력받는다.

2. 그래프를 BFS 또는 DFS 알고리즘을 통해 탐색을 진행한다. (각각 코딩하여 진행하였음)

지금까지 bfs와 dfs를 여러문제 풀어봤다. 이 문제에서는 풀이를 그냥 형식적이지 않고 내 생각 그대로를 표현해보겠다.

0,0 부터 h,w까지 bfs,dfs 탐색을 통해 전체탐색을 진행한다. 각각 노드에 대해 8방면(상하좌우 + 대각선 4방향) 체크를 하며 체크시 방문하지 않고, 땅이 존재한다면(= 조건) 방문한다. 
결과적으로 A 노드를 탐색했을때 8방면에 대해 탐색을 진행하는데 조건이 만족한다면 계속 탐색한다. 즉, 조건이 만족한다는 것은 이어진 땅이라는 뜻이므로, 카운트는 세지않는다. 조건이 만족하지 않으면 bfs 함수에서 나와 다시 메인문의 다음 노드를 찾게되는데, 방금전 방문한 노드를 제외하고 탐색을 이어나가게 된다. 이때 카운트가 들어가서 다음 땅을 찾게되는 것이다.

3. 섬의 개수를 출력

4. (테스트 케이스가 1 이상이므로) 그래프 및 방문기록 초기화

 

※ 테스트 케이스가 여러개일때는 초기화를 잊지말자

※ 이중 포문을 쓸때는 i와 j... 잘 구분해서 쓰자(i,i로 잘못쓴줄 모르고 한참 찾음..ㅎㅎ)

 

소스 코드

#include <iostream>
#include <queue> // use bfs algorithm
#include <stdio.h> // use printf, scanf
#include <cstring> // use memset
 
#define MAX_SIZE 50
 
using namespace std;
 
int w, h;
int NumberOfLand = 0;
int graph[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
 
// 우,하,좌,상,우상,우하,좌상,좌하
int dw[8] = { 1, 0, -1, 0 , 1 , 1,-1,-1 };
int dh[8] = { 0, 1, 0 , -1, -1, 1,-1, 1 };
 
void bfs(int h, int w) {
    queue< pair<int, int> > q; // 이용할 큐, (h,w)
    q.push(make_pair(h, w));
    
    // 처음 h,w를 방문 했기 때문에
    visited[h][w] = true;
    while (!q.empty()) {
        // 큐의 현재 원소를 꺼내기
        h = q.front().first;
        w = q.front().second;
        q.pop();
 
        // 해당 위치의 주변을 확인
        for (int i = 0; i < 8; i++) {
            int nh = h + dh[i];
            int nw = w + dw[i];
 
            // 지도를 벗어나지 않고,
            if (0 <= nw && 0 <= nh && nw < MAX_SIZE && nh < MAX_SIZE) {
                // 섬이면서 방문하지 않았다면
                if (graph[nh][nw] && !visited[nh][nw]) {
                    visited[nh][nw] = true;
                    q.push(make_pair(nh, nw));
                }
            }
        }
    }
}
 
void dfs(int h, int w) {
    // 처음 h,w를 방문 했기 때문에
    visited[h][w] = true;
 
    // 해당 위치의 주변을 확인
    for (int i = 0; i < 8; i++) {
        int nh = h + dh[i];
        int nw = w + dw[i];
 
        // 지도를 벗어나지 않고,
        if (0 <= nw && 0 <= nh && nw < MAX_SIZE && nh < MAX_SIZE) {
            // 섬이면서 방문하지 않았다면
            if (graph[nh][nw] && !visited[nh][nw]) {
                visited[nh][nw] = true;
                dfs(nh, nw);
            }
        }
    }
}
 
int main() {
    while (1) {
        scanf("%d %d", &w, &h);
        /* w=0 이면서 h=0이면 종료 */
        if (!w && !h) break;
 
        /* 그래프 정보 입력 */
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%1d", &graph[i][j]);
            }
        }
 
        /* 그래프를 BFS 또는 DFS를 통해 탐색 */
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 땅이 존재하고(1), 방문하지 않았을 때(0)
                if (graph[i][j] && !visited[i][j]) {
                    NumberOfLand++;
                    bfs(i,j);
                    //dfs(i, j);
                }
            }
        }
 
        /* 섬의 개수를 출력 */
        printf("%d\n", NumberOfLand);
 
        /* 그래프 및 방문기록, 섬의 개수 초기화 */
        memset(graph, false, sizeof(graph));
        memset(visited, false, sizeof(visited));
        NumberOfLand = 0;
    }
    return 0;
}