백준 2589 보물섬 (C++)

2589번: 보물섬

bfs를 이용한 문제이다. 먼저 주어진 지도를 입력받을 때 땅을 1, 바다를 0으로 저장하였다. 그리고 각 위치에서의 최단 거리를 구하기 위해 반복문을 돌며 땅에 해당하면 모두 bfs를 사용했다. bfs에서는 반복문마다 res에 최단 거리를 저장하여 최단 거리 중 가장 긴 거리를 구하여 출력해주었다.
전형적인 bfs와 브루트포스 문제이기에 금방 풀 수 있었다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int R, C, res = 0;
int A[50][50];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool check[50][50];

void bfs(int a, int b) {
    queue<pair<pair<int, int>, int>> q;

    q.push({ { a, b }, 0});
    check[a][b] = true;

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int count = q.front().second;

        q.pop();

        res = max(res, count);

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
            if (A[ny][nx] == 0) continue;
            if (check[ny][nx]) continue;

            q.push({ {ny,nx},count + 1 });
            check[ny][nx] = true;
        }
    }
}

void solution(){
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i][j] == 1) {
                memset(check, 0, sizeof(check));
                bfs(i, j);
            }
        }
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < C; j++) {
            if (s[j] == 'W') {
                A[i][j] = 0;
            }
            else {
                A[i][j] = 1;
            }
        }
    }

    solution();

    return 0;
}