[백준] 보물섬 2589번 (c++)

출처 : 2589번: 보물섬 (acmicpc.net)

2589번: 보물섬

풀이 방법

그래프 문제인데 시작점을 여러번 바꿔가면서 bfs를 수행하여야 한다.

그래서 완전 탐색(Brute Force)를 이용하여 육지에서의 거리가 가장 먼 값을  구하여 답으로 출력 해야한다.

여기서 visited에 거리를 저장하는데 시작점을 1로 두어야 다시 시작점을 방문하는 오류를 줄일수 있어

시작점의 visited 값을 1로 설정한뒤 마지막에 답을 출력할때 -1을 해준다.

#include <bits/stdc++.h>

using namespace std;

int L,H;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
vector<string> board;
int visited[51][51];
int ans = 0;

void bfs(int y, int x) {
    queue<pair<int ,int>> q;
    visited[y][x] = 1;
    q.push(make_pair(y, x));
    while (!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (ny >= 0 && ny < H && nx >= 0 && nx < L) {
                if (board[ny][nx] == 'L' && visited[ny][nx] == 0) {
                    visited[ny][nx] = visited[yy][xx] + 1;
                    if (ans < visited[ny][nx]) {
                        ans = visited[ny][nx];
                    }
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
}
int main() {
    cin >> H >> L;
    for (int i = 0;i < H;i++) {
        string in;
        cin >> in;
        board.push_back(in);
    }
    for (int i = 0;i < H;i++) {
        for (int k = 0;k < L;k++) {
            if (board[i][k] == 'L') {
                memset(visited, 0, sizeof(visited));
                bfs(i, k);
            }
        }
    }
    cout << ans-1;
    return 0;
}