4963 : 섬의 개수 (C++)

4963번: 섬의 개수

---

이번 문제는 보통 문제들과는 달리 8방향으로 이동할 수 있다.

보통 상하좌우라면 이 문제는 대각선 방향으로도 갈 수 있어서 4방향으로 더 검사를 진행해야한다.

BFS방식으로 문제를 해결하였다.

#include<iostream>
#include<queue>

using namespace std;

#define MAX 50

int w, h;
int map[MAX][MAX];
bool visit[MAX][MAX];

int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, 1, -1, -1};

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = true;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
            
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w)
                continue;
            if(map[nx][ny] == 1 && visit[nx][ny] == false) {
                q.push({nx, ny});
                visit[nx][ny] = true;
            }
        }
    }
}

int main() {
    while(true) {
        fill(map[0], map[50], 0);
        fill(visit[0], visit[50], 0);

        cin >> w >> h;

        if(w == 0 && h == 0) {
            break;
        }

        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j];
            }
        }

        int cnt = 0;

        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] == 1 && visit[i][j] == false) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

 

밑에는 DFS 함수

void dfs(int x, int y) {
    visit[x][y] = true;
    
    for(int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < h && ny >= 0 && ny < w) {
            if(map[nx][ny] == 1 && visit[nx][ny] == false) {
                dfs(nx, ny);
            }
        }
    }
}