섬의개수 - 백준(4963) [99클럽 코테 TIL]

섬의 개수

기본적인 DFS 문제였다

해결방안

• 섬의 개수를 세야 하기 때문에 DFS 알고리즘을 사용한다

• 문제에서 대각선도 걸어갈 수 있다했기 때문에 대각선도 탐색하는 DFS 알고리즘을 사용한다

#include <bits/stdc++.h>
using namespace std;

const int dy[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dx[] = {0, 1, 0, -1, -1,  1, 1, -1};
const int MAX = 55;
int a[MAX][MAX];
bool visited[MAX][MAX];

int n, m;

void dfs(int y, int x) {
    visited[y][x] = true;
    for (int i = 0; i < 8; i++) {  // 8방향 모두 검사
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (!visited[ny][nx] && a[ny][nx] == 1) {
            dfs(ny, nx);
        }
    }
}

int main() {
    while (true) {
        int cnt = 0;
        cin >> m >> n;
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
        memset(visited, 0, sizeof(visited));
    }
    return 0;
}

항상 가로 세로만 탐색하는 문제를 풀다가 대각선에 잠깐 멈칫했지만 dy, dx 배열에 그에 맞게 수를 추가주면 되는 문제였다.
각 테스트 케이스마다 visited 배열을 초기화 하는 것 또한 중요!!