보물섬 2589

문제

접근 방법

크기가 50 이하가 아니라면 힘든 방법이지만 모든 타일에 대해서 BFS를 시도하는 방법으로 접근하였다.
시간복잡도를 계산하자면 한 변을 N이라 할 때 두 변은 N^2이다. BFS를 할 때 모두가 육지라면 N^2만큼 할 것이다.
모든 타일에 대해서 BFS를 시도하기에 N^2만큼 BFS를 한다.
즉 모든 타일 (N^2)의 BFS(N^2)로 O(N^4)라는 시간복잡도가 나오는 것이다.
시간복잡도만 보면 오답에 가까운 방식이지만 제한사항인 50 이하가 붙었기에 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int L, W, ret = 0;
    cin >> L >> W;
    vector<vector<char>> map(L, vector<char>(W));
    vector<vector<bool>> visted;
    queue<pair<int, pair<int, int>>> bfs;
    for (int i = 0; i < L; ++i)
        for (int j = 0; j < W; ++j)
            cin >> map[i][j];
    for (int i = 0; i < L; ++i)
        for (int j = 0; j < W; ++j)
        {
            if (map[i][j] == 'W')
                continue;
            visted = vector<vector<bool>>(L, vector<bool>(W));
            bfs.push({0, {i, j}});
            visted[i][j] = true;
            while (!bfs.empty())
            {
                auto cur = bfs.front();
                bfs.pop();
                for (int i = 0; i < 4; ++i)
                {
                    pair<int, pair<int, int>> next = {cur.first + 1, {cur.second.first + dy[i], cur.second.second + dx[i]}};
                    if (next.second.first < 0 || next.second.second < 0 || next.second.first >= L || next.second.second >= W)
                        continue;
                    if (visted[next.second.first][next.second.second] || map[next.second.first][next.second.second] == 'W')
                        continue;
                    visted[next.second.first][next.second.second] = true;
                    ret = ret > next.first ? ret : next.first;
                    bfs.push(next);
                }
            }
        }
    cout << ret;
}

풀이

오랜만에 푸는 BFS 문제인 것 같다.
이 문제는 어려울 것 같다는 생각이 들어서 포기하게 만드는 그런 부류의 문제인 것 같다.
나 또한 처음 보고 불가능하지 않을까 싶었다. 시간복잡도를 통한 유추에 대해서 더욱 생각해보게 해주는 문제였다.