백준 2589번 보물섬

🔒[문제 url]

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

🔑알고리즘

모든 L 지점에 대하여 BFS 탐색을 진행하여,
각 지점으로부터 가장 멀리있는 L까지의 거리를 반환한다.
그중 최대값이 출력 답안이 된다.

BFS를 진행하기 전 중복 방지 배열 visited를 초기화해주어야함에 주의하자.

🐾부분 코드

int BFS(int a, int b)
{
    int dist = 0; // 반환할 최대 거리

    queue<pair<int,int>> q;
    q.push({a,b});
    visited[a][b] = 0;

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < n && 0 <= ny && ny < m)
            {
                if(visited[nx][ny] == -1 && map[nx][ny] != 'W')
                {// 방문하지 않은 육지(L)라면
                    q.push({nx,ny});
                    visited[nx][ny] = visited[x][y] + 1;
                    dist = max(dist, visited[nx][ny]);
                }
            }
        }// for end
    }

    return dist;
}

<BFS 함수>
갈 수 있는 L 지점 중 최대 거리를 반환한다.

void SOLVE()
{
    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(map[i][j] == 'L')
            {
                memset(visited, -1, sizeof(visited));
                ans = max(ans, BFS(i,j));
            }
        }


    cout << ans;

}

<BFS 반복>
L인 모든 지점에 대해 BFS를 진행한다.
visited 초기화에 유의하자.

🪄전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

int n, m;
char map[51][51];
int visited[51][51];

// 우 하 상 좌
int dir[4][2] = {{0,1},{1,0},
                 {-1,0},{0,-1}};

void INPUT()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%1s", &map[i][j]);
}

int BFS(int a, int b)
{
    int dist = 0; // 반환할 최대 거리

    queue<pair<int,int>> q;
    q.push({a,b});
    visited[a][b] = 0;

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < n && 0 <= ny && ny < m)
            {
                if(visited[nx][ny] == -1 && map[nx][ny] != 'W')
                {// 방문하지 않은 육지(L)라면
                    q.push({nx,ny});
                    visited[nx][ny] = visited[x][y] + 1;
                    dist = max(dist, visited[nx][ny]);
                }
            }
        }// for end
    }

    return dist;
}

void SOLVE()
{
    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(map[i][j] == 'L')
            {
                memset(visited, -1, sizeof(visited));
                ans = max(ans, BFS(i,j));
            }
        }


    cout << ans;

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

매우 흔하디 흔한 그래프 문제이니 잘 숙지하도록 하자.