2589번 보물섬

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

3가지 시도를 했었다.

1. 모든 'L'의 좌표를 vector에 담아 이중 for문으로 a정점에서 b점으로 가는 거리를 구하기 -> 시간 초과

2. 어떤 한 정점에서 가장 멀리 떨어진 정점으로 이동하고, 그 정점에서 다시 가장 멀리 떨어진 정점과의 거리 구하기 -> 오답

4 4
LLLL
LWLW
LLLW
LWWW

답 : 6

오답 : 4

3. 한 정점 'L'에서 끝까지 퍼져 나가면서 최댓값 구하기 -> 정답

2번에 대한 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 55
#define INF 2e9
 
int R, C;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max], use[Max][Max];
char m[Max][Max];
 
pair<int, int> getPosition(int ty, int tx)
{
    int temp = 0, dist = 0;
    pair<int, int> ret = { -1, -1 };
 
    visit[ty][tx] = true;
    queue<pair<int, int> > q;
 
    q.push({ ty, tx });
 
    while (!q.empty())
    {
        int qs = q.size();
        
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (temp < dist) {
                temp = dist;
                ret.first = r;
                ret.second = c;
            }
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || m[y][x] == 'W') {
                    continue;
                }
 
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
 
        ++dist;
    }
 
    return ret;
}
 
int getDistance(int sy, int sx)
{
    int ret = 0, dist = 0;
 
    memset(use, false, sizeof(use));
    use[sy][sx] = true;
 
    queue<pair<int, int> > q;
    q.push({ sy, sx });
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            ret = max(ret, dist);
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || use[y][x] || m[y][x] == 'W') {
                    continue;
                }
 
                use[y][x] = true;
                q.push({ y, x });
            }
        }
 
        ++dist;
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    cin >> R >> C;
 
    int ans = 0;
 
    for (int i = 0; i < R; i++) {
        scanf("%s", &m[i][0]);
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!visit[i][j] && m[i][j] == 'L') {
                pair<int, int> g = getPosition(i, j);
                ans = max(ans, getDistance(g.first, g.second));
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}

3번에 대한 정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 55
#define INF 2e9
 
int R, C;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max];
char m[Max][Max];
 
int bfs(int sy, int sx)
{
    int dist = 0;
 
    memset(visit, false, sizeof(visit));
    visit[sy][sx] = true;
 
    queue<pair<int, int> > q;
    q.push({ sy, sx });
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || m[y][x] == 'W') {
                    continue;
                }
 
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
 
        ++dist;
    }
 
    return dist - 1;
}
 
int main()
{
    cin.tie(0);
 
    for (int i = 0; i < Max; i++) {
        for (int j = 0; j < Max; j++) {
            visit[i][j] = INF;
        }
    }
 
    cin >> R >> C;
 
    int ans = 0;
 
    for (int i = 0; i < R; i++) {
        scanf("%s", &m[i][0]);
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j] == 'L') {
                ans = max(ans, bfs(i, j));
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}