[BOJ 33656 // C++] Island Exploration

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 33656번 문제인 Island Exploration이다.
문제는 아래 링크를 확인하자.

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

 

전형적인 2차원 격자에서의 connected component의 크기를 구하는 문제이다.

 

이 유형의 문제는 flood-fill 계열의 탐색으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int R, C, sR, sC, ans = 1;
char board[100][100];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<pair<int, int>> que;

void bfs() {
    que.push(make_pair(sR, sC));
    board[sR][sC] = '.';
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (board[rr][cc] != '#') continue;
            board[rr][cc] = '.', ans++;
            que.push(make_pair(rr, cc));
        }
    }
}

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

    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> board[r][c];
            if (board[r][c] == 'S') sR = r, sC = c;
        }
    }

    bfs();
    cout << ans;
}