4963 섬의 개수

4963. 섬의 개수 / c++ / Silver2 / 9분

문제

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

1. h, w 크기의 board가 있다.
2. 그 칸이 땅이면 이동할 수 있고, 상하좌우대각선으로 이동할 수 있을 때,
3. 해당 칸에서 이동할 수 있는 모든 칸은 같은 섬이라고 정의한다.
4. 이 때, 총 섬의 갯수를 출력하라.

접근 방식

그래프, DFS

1. board를 전체적으로 순회하면서 만약 섬이라면 answer++ 하고 DFS순회
2. DFS 순회 시 현재 지역을 바다로 만듦 (메모리 효율)
3. answer 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

int board[50][50];
int w, h;
int answer;
int dy[8] = { -1, -1, -1, 1, 1, 1, 0, 0 };
int dx[8] = { -1, 0, 1, -1, 0, 1, -1, 1 };

void DFS(int y, int x)
{
    board[y][x] = 0;
    for (int i = 0; i < 8; ++i)
    {
        int nextY = y + dy[i];
        int nextX = x + dx[i];

        if (nextY < 0 || nextY >= h || nextX < 0 || nextX >= w) continue;
        if (board[nextY][nextX] == 0) continue;
        DFS(nextY, nextX);
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (true)
    {
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        answer = 0;
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                cin >> board[i][j];
            }
        }

        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                if (board[i][j] == 1)
                {
                    answer++;
                    DFS(i, j);
                }
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

다시 생각해 볼 점

1. 단순하 DFS 문제
2. 탐색에 대각선방향이 추가된 것만 추가 처리해주면 됐다.