문제

문제 링크

해설

• 보물의 위치가 주어지고, 시작 위치에서 보물까지 최단거리를 구하는 일반적인 문제와 달리 이 문제는 시작위치와 도착위치가 정해져있지 않습니다.
• 그러므로 임의의 육지 상 좌표에 대해 BFS를 수행해 갈 수 있는 모든 좌표의 최단거리를 구하고 그 중 가장 긴 거리를 구하면 해당 지점을 시작지점으로, 가장 긴 거리의 좌표를 보물의 위치로 삼으면 됩니다.
• 이 아이디어만 떠올렸다면 나머지는 정말 간단합니다.
  • 입력받은 문자열 중 ‘W’ 문자에 대한 좌표를 모두 따로 저장합니다.
  • 모든 육지 좌표에 대해 BFS를 수행하고, 가장 긴 보물의 위치를 구합니다.
  • 매 BFS 수행 후에는 memset() 또는 fill() 함수를 이용해 visited 표시를 초기화해야 하는 것을 잊지 맙시다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, M, answer;
bool map[52][52];
bool visited[52][52];
vector<pair<int, int>> lands_pos;

void BFS(int sy, int sx) {
    queue<tuple<int, int, int>> q;
    q.emplace(sy, sx, 0);
    visited[sy][sx] = true;

    while (!q.empty()) {
        int cy, cx, cd;
        tie(cy, cx, cd) = q.front();
        q.pop();
        answer = max(answer, cd);
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            if (map[ny][nx] && !visited[ny][nx]) {
                q.emplace(ny, nx, cd + 1);
                visited[ny][nx] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M;
    lands_pos.reserve(N * M);
    for (int y = 1; y <= N; y++) {
        string row;
        cin >> row;
        for (int x = 1; x <= M; x++) {
            if (row[x - 1] == 'L') {
                map[y][x] = true;
                lands_pos.emplace_back(y, x);
            }
        }
    }
    for (int i = 0; i < lands_pos.size(); i++) {
        BFS(lands_pos[i].first, lands_pos[i].second);
        memset(visited, false, sizeof(visited));
    }
    cout << answer << '\n';
    return 0;
}

소스코드 링크

결과