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

문제링크 : https://www.acmicpc.net/problem/2589

2589번: 보물섬

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int H, W, result = 0;
char arr[51][51];
int visited[51][51];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


void bfs(int y, int x)
{
    queue<pii>q; 
    visited[y][x] = 1; //방문처리를 위한 처음 1표시 
    q.push({y, x});

    while(!q.empty())
    {
        auto [yy, xx] = q.front(); q.pop();
        result = max(result, visited[yy][xx]); //거리 저장

        for(int i=0; i<4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];

            if(ny < 0 || nx < 0 || ny >=H || nx >= W) continue;
            if(arr[ny][nx]!='L' || visited[ny][nx]) continue;
            visited[ny][nx] = visited[yy][xx] + 1; //거리 증가
            q.push({ny, nx});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> H >> W;
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            if(arr[i][j]=='L') //L일떄마다 탐색
            {
                memset(visited, 0, sizeof(visited)); //매번 초기화
                bfs(i, j);
            }
        }
    }

    cout << result-1; //처음 1제거후 출력
    return 0;
}

현재 위치가 L일 때마다 매번 거리를 확인하고 이렇게 확인한 거리가 최대치일때를 출력해주면 된다.

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다라는 문장에 유의하여야 한다. (max로 거리 저장하는 이유)

 

처음 visited[y][x]를 1로 꼭 초기화를 해주어야 한다.

해당 배열은 방문체크와 동시에 계산한 거리를 담아준다.

처음 거리는 0이므로  0을 저장하고 풀었다가 엄청 틀리고 뒤늦게 알았는데 방문체크 역할도 하기 때문에 1을 저장하고 마지막 결과값에서 -1을 해줘야 한다.

 

이때문에 엄청 틀렸다.