백준 4963 - 섬의 개수

문제

 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

풀이

 

DFS 탐색의 개념을 이용하는 문제이다. 값이 1인 좌표에서 상하좌우, 대각선으로 모두 검사해서 1인 좌표가 있다면, 그 좌표에서 다시 DFS 탐색을 진행하면 된다. 탐색을 진행한 좌표는 0으로 바꿔서 재방문을 막아야 한다.

 

1. main 함수에서 이중 for문에서 좌표 값이 1인 지점에서 DFS 탐색을 진행한다.

2. DFS 탐색을 진행한 좌표 값을 0으로 바꾼다.

3. 상하좌우, 대각선을 검사해서 1인 좌표에서 DFS 탐색을 진행한다.

4. main 함수에서 이중 for문이 끝날때까지 1, 2, 3 반복

 

 

코드

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int w, h;
int graph[52][52];
int cnt;
 
void dfs(int i, int j)
{
    graph[i][j] = 0;
 
    if (graph[i - 1][j]) dfs(i - 1, j);
    if (graph[i + 1][j]) dfs(i + 1, j);
    if (graph[i][j - 1]) dfs(i, j - 1);
    if (graph[i][j + 1]) dfs(i, j + 1);
 
    if (graph[i - 1][j - 1]) dfs(i - 1, j - 1);
    if (graph[i - 1][j + 1]) dfs(i - 1, j + 1);
    if (graph[i + 1][j - 1]) dfs(i + 1, j - 1);
    if (graph[i + 1][j + 1]) dfs(i + 1, j + 1);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    while (1)
    {
        cin >> w >> h;
        if (!w && !h) break;
 
        memset(graph, 0, sizeof(graph));
        cnt = 0;
 
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++) cin >> graph[i][j];
 
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
                if (graph[i][j])
                {
                    dfs(i, j);
                    cnt++;
                }
 
        cout << cnt << '\n';
    }
 
    return 0;
}