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

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

 

 

#문제 간단 정리

bfs를 통한 거리 문제

 

#문제 해결 방법

 

이 문제는 bfs를 통해서

가장 먼 거리의 위치 를 찾는 문제이다

 

전형적이 bfs에서 조금 활용이라고 볼 수 있다.

 

모든 육지 노드에 대해 돌면서 그 육지에서

가장 먼 노드를 찾고

 

가장 먼 거리를 변수에 저장하면 된다.

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { -1,0,1,0 };
vector<vector<char>> tMap;
int maxDist;

int bfs(int inputY, int inputX) {
    //좌표,거리
    queue<pair<int, int>> q;
    vector<vector<int>> dist(n, vector<int>(m, -1));

    q.push({ inputY,inputX });
    dist[inputY][inputX] = 0;
    int mdist = 0;

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

        q.pop();

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

            if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                if (tMap[ny][nx] == 'L') {
                    if (dist[ny][nx] == -1 || dist[ny][nx] > dist[y][x] + 1) {
                        q.push({ ny,nx });
                        dist[ny][nx] = dist[y][x] + 1;
                    }
                }
            }
        }

    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mdist = max(mdist, dist[i][j]);
        }
    }

 /*   for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    cout << '\n';*/
    return mdist;
}

int main()
{

    cin >> n >> m;

    tMap.resize(n, vector<char>(m));
    maxDist = 0;

    for (int i = 0; i < n; i++) {
        string input;
        cin >> input;

        for (int j = 0; j < m; j++) {
            tMap[i][j] = input[j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tMap[i][j] == 'L') {
                maxDist = max(bfs(i, j), maxDist);
            }
        }
    }

    cout << maxDist << '\n';

}