[BOJ] 2589 : 보물섬

Drakk·2021년 7월 13일

2589 BFS C boj 백준 보물섬 브루트포스 알고리즘

알고리즘 문제풀이

목록 보기

4/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

🧺출력
첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

🔋예제 입출력

🔮예제 입력1

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

🔮예제 출력1
8

💉문제 분석

🔋분류

BFS, 브루트포스

🔋난이도

골드V

💉문제 풀이

🔋해법

우선 이 문제는 기존의 그래프탐색문제와는 다른점이 있는데,
시작점과 도착점이 존재하지않습니다.
그러면 어떻게 최단거리를 찾아야할지 생각해보니...

그냥 무식하게 모든지점에 대해 최단거리를 찾은뒤, 모든지점에 대한 최단거리들의 최댓값을 얻으면 그 최댓값이 답이됩니다.

우선은 시간과 효율을 늘리기위해 'L'로 시작하는 지점만 탐색하구요.
저는 char 2차원배열보다는 그냥 std::string이 편할것같아서 그렇게 썼습니다.

최단거리는 cost[다음 y좌표][다음 x좌표]에서 1을 뺀값이 됩니다.

🔋소스코드

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

#define MAX (50)

std::string adj[MAX];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int bfs(int M, int N, int sx, int sy){
    int cost[MAX][MAX] = { 0 };
    int smin = 0;

    std::queue<std::pair<int, int>>q;
    q.push(std::make_pair(sx, sy));
    cost[sy][sx] = 1;
    
    while(!q.empty()){
        int curx = q.front().first;
        int cury = q.front().second;
        q.pop();

        for(int i=0;i<4;++i){
            int nexx = curx + dx[i];
            int nexy = cury + dy[i];

            if(nexx < 0 || nexy < 0 || nexx >= M || nexy >= N) continue;
            if(adj[nexy][nexx] == 'L' && cost[nexy][nexx] == 0){
                cost[nexy][nexx] = cost[cury][curx] + 1;
                q.push(std::make_pair(nexx, nexy));
                smin = std::max(smin, cost[nexy][nexx]);
            }
        }
    }

    return smin - 1;
}

int main(){
    int N, M, smax = 0;
    std::cin >> N >> M; // N: 세로, M: 가로

    for(int i=0;i<N;++i) std::cin >> adj[i];

    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
        	if(adj[i][j] == 'L') smax = std::max(smax, bfs(M, N, j, i)); // M, j: x, N, i: y
        }
    }

    std::cout << smax;
}