2589번 보물섬

BFS 문제이다.

'L'의 위치를 position에 담아 놓고, BFS 내에 있는 queue에 push 후에 바로 position을 pop하는 식으로

순서대로 L의 갯수 만큼 BFS를 실행하면 된다.

71번 째 줄에 +1을 한 이유는 dist 배열의 초기값은 -1이기 때문이다.

이 문제에서 기억해야할 것

1. 방문 여부를 굳이 visit를 써서 할 필요가 없다. 거리 그 자체(dist)를 해도 된다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
char map[51][51];
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int N = 0, M = 0;
 
queue<pair<int, int> > position;
 
int result = -987654321;
 
int BFS()
{
    queue<pair<int, int> > q;
 
    int dist[51][51] = { 0, };
 
    memset(dist, -1, sizeof(dist));
 
    q.push({ position.front() });
 
    position.pop();
 
    visit[q.front().first][q.front().second] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            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 >= N || x < 0 || x >= M || dist[y][x] > -1 || map[y][x] == 'W') continue;
 
                dist[y][x] = dist[r][c] + 1;
 
                q.push({ y,x });
            }
 
        }
    }
 
    int m = -987654321;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            m = max(m, dist[i][j] + 1);
        }
    }
 
    return m;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
 
            if (map[i][j] == 'L')
            {
                position.push({ i,j });
            }
        }
    }
 
    int pSize = position.size();
 
    while (pSize--)
    {
        result = max(result, BFS());
    }
 
    printf("%d\n", result);
 
    return 0;
}