백준 [2589] 보물섬

c++ 기준 단순 bfs로 푼다면 100~120ms의 시간으로 풀 수 있지만,

 

그래프 지름에 대해서 생각해 본다면 더욱 빠르게 풀 수 있다. (20ms정도)

1이 육지, 0이 바다라고 하고 지도가 다음과 같다면 3가지 조건에 대해 생각해볼 수 있다.

반대 방향도 됨

1. 어떤 지점의 위, 아래에 땅이 있을 때

빨간 곳처럼 위 아래로 땅이 있는 경우, 해당 지역은 단순히 거쳐가는 지역이된다

실제로 찍어보면 알겠지만 해당 지점에서 시작한 거보다 그 위 아래에서 시작한게 더 크다

 

2. 어떤 지점의 좌우에 땅이 있을 때

이 부분도 마찬가지로 좌우에서 시작한게 해당 지역에서 시작한 거보다 더 크다

 

3. 상하, 좌우가 아닌 2갈래로 퍼지는 곳

위 오른쪽, 위, 왼쪽 처럼 x,y 축으로 한 방향씩 갈라지는 곳이다

사진처럼 아래, 오른쪽으로 갈라지는 경우 2가지 관점에서 생각해 볼 수 있다

아래, 오른쪽으로     갈라지는 경우

 

1. 밑줄친 0이 1이라 가정할 때 (사실 문제에선 사이클이 허용되지 않는다.)

해당 지역이 1이 되버리면 하나의 사이클이 되고, 이렇게 되면

해당 사이클의 어떤 지역에서 시작해도 값은 같으므로 탐색 큐에서 빼도 된다.

 

2. 밑줄친 0이 그냥 0일 때

1의 조건처럼 이어지지 않는 경우 아래, 오른쪽 방향에 땅이 있다면 해당 지역은

그냥 거쳐가는 지역이 된다.

여기서 주의할 점이, 꺾이는 4가지 경우에 대해 하나만 배제해야 하는 것이다.

2개 이상으로 할 경우

[[1,1],[1,1]] 인 경우에서 오답이 난다.

 

이 3가지 조건을 check란 함수에 구현한 코드이다

3번 조건 같은 경우엔 위, 오른쪽이든 아래, 오른쪽이든 하나의 경우에 대해서만 작성해주면 된다

하나 더 추가해주면 틀림

 

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

#define MAX 64

typedef struct
{
    int y, x, cost;
}DIR;

int L, W, ans = 0;
DIR dir[4] = { {1,0},{-1,0},{0,1},{0,-1} };
int map[MAX][MAX];
queue<DIR> land;


int search(int y, int x);
int check(int y, int x);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> L >> W;
    for (int i = 1; i <= L; i++)
    {
        cin >> str;
        for (int j = 1; j <= W; j++) {
            if (str[j - 1] == 'L') {
                map[i][j] = 1;
            }
        }
    }

    for (int i = 1; i <= L; i++)
        for (int j = 1; j <= W; j++)
            if (map[i][j] == 1)
                check(i, j);

    while(!land.empty())
    {
        search(land.front().y, land.front().x);
        land.pop();
    }
    cout << ans;
    return 0;
}

int check(int y, int x)
{
    /* 위 아래에 땅이 있으면 해당 위치는
       그냥 거쳐가는 지역이라 큐에 안 넣어도 됨 */
    if (map[y - 1][x] == 1 && map[y + 1][x] == 1)
        return 0;
    /* 마찬가지로 좌우에 땅이 있으면 해당 위치는
       그냥 거쳐가는 지역이라 큐에 안 넣어도 됨 */
    if (map[y][x - 1] == 1 && map[y][x + 1] == 1)
        return 0;
    /* 위의 두 조건을 제외하고 아래, 오른쪽같이 2갈래 방향으로 갈라질 때
       이 갈라진 길이 서로 만난다면 해당 사이클의 아무 지점에서 탐색을 해도 값이 같음
       만약 만나지 않는다면 갈라진 두 지점의 종점끼리의 거리가 더 길기 때문에
       해당 위치는 거쳐가는 자리가 되버린다
    */
    if (map[y][x + 1] == 1 && map[y + 1][x] == 1)
        return 0;
    land.push({ y,x,0 });
    return 0;
}

int search(int y, int x)
{
    bool visit[MAX][MAX] = { 0, };
    int hereX, hereY, hereC, thereX, thereY;
    queue<DIR> q;
    q.push({ y,x });
    visit[y][x] = 1;
    while (!q.empty())
    {
        hereY = q.front().y;
        hereX = q.front().x;
        hereC = q.front().cost;
        q.pop();
        ans = max(ans, hereC);
        for (int d = 0; d < 4; d++)
        {
            thereY = hereY + dir[d].y;
            thereX = hereX + dir[d].x;
            if (!(0 < thereX && thereX <= W && 0 < thereY && thereY <= L))
                continue;
            if (visit[thereY][thereX] || map[thereY][thereX] == 0)
                continue;
            visit[thereY][thereX] = 1;
            q.push({ thereY, thereX, hereC + 1 });
        }
    }
    return 0;
}