4963번-섬의 개수

문제

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

4963번: 섬의 개수

---

접근방법

1) 접근 사고

1. 섬을 8가지 방향으로 탐색을 합니다.

2. 탐색을 하면서 방문한 섬은 visited배열을 사용해서 방문 체크를 진행해줍니다.

3. 시도한 BFS 횟수가 섬의 개수를 의미하는것을 알 수 있습니다.

 

2) 시간 복잡도

O(V + E)

 

3) 실수

r과 c의 위치가 바껴서 나온다. 문제 설명이 너무 불친절한거 아닌가..

예제를 다시 보고 입력 부분이 잘못되었다는것을 알 수 있었다.

 

4) 배운점

 

5) PS

---

정답 코드

#include <bits/stdc++.h>

using namespace std;

int r, c;
const int MAX = 55;
int board[MAX][MAX];
bool visited[MAX][MAX];

int moveY[] = {-1,-1,-1,0,0,1,1,1};
int moveX[] = {-1,0,1,-1,1,-1,0,1};

void BFS(int i, int j){
    queue<pair<int,int>> q;
    q.push({i, j});
    visited[i][j] = true;

    while(!q.empty()){
        auto[y, x] = q.front();
        q.pop();

        for(int d = 0; d < 8; d++){
            int ny = y + moveY[d];
            int nx = x + moveX[d];
            if(ny >= 0 && ny < r && nx >= 0 && nx < c){
                if(!visited[ny][nx] && board[ny][nx]){
                    visited[ny][nx] = true;
                    q.push({ny, nx});
                }
            }
        }
    }
}

int pro(){
    int count = 0;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++) {
            if (!visited[i][j] && board[i][j]) {
                BFS(i, j);
                count++;
            }
        }
    }
    return count;
}

void input(){
    fill(&board[0][0], &board[r][c + 1], 0);
    memset(visited, false, sizeof(visited));
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> board[i][j];
        }
    }
}

int main(){

    while(1){
        cin >> c >> r;
        if(r == 0 && c == 0)
            break;
        input();
        int ans = pro();
        cout << ans <<"\n";
    }
}