[백준/Baekjoon] 4963 섬의 갯수 C++ :: BFS

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

4963번: 섬의 개수

---

1. Logic

정사각형이 같은 섬에 잇는 조건은 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다. 즉 8방향 탐색을 해서 섬의 갯수를 구해주면 된다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int graph[51][51];
bool vis[51][51];

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

int w, h;

void bfs(int y, int x) {
    queue<pair<int, int>> q;
    
    q.push({y, x});
    vis[y][x] = true;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        
        q.pop();
        
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
            if(vis[ny][nx]) continue;
            if(graph[ny][nx] == 0) continue;
            
            q.push({ny, nx});
            vis[ny][nx] = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    while(true) {
        memset(graph, 0, sizeof(graph));
        memset(vis, false, sizeof(vis));
        
        int cnt = 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 >> graph[i][j];
            }
        }
        
        for(int i =0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(vis[i][j]) continue;
                if(graph[i][j] == 0) continue;
                
                bfs(i, j);
                cnt++;
            }
        }
        
        cout << cnt << "\n";
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90