💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 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;
}

처음에 좌표 시작점을 (0, 0)이아닌 (1, 1)로 해서 좀 헤맸습니다.
방법은 맞았는데, 계속틀렸다고 나오길래, 혹시나해서 시작점을 (0, 0)부터 시작했더니, 되더라구요...

저는 이 문제랑 헷갈려서
처음방식은 0에서 1부터 더해나가는것이아닌, 모든점에 대한 비용을 INF값으로 채우고,
시작점에 대한 비용을 0으로 바꾼뒤,

조건문을 "cost[nexy][nexx] >= cost[nexy][nexx] + 1"으로 했더니, 시간초과가나더군요...

왜냐하면 사전에 cost값을 모두 INF값으로 주변서 쓸데없이 반복문을 사용했습니다.

그래도 재미있었습니다.
문제푼 시간은 보시다시피, 25분정도 걸렸네요.

💉마치며...

하...ㅠㅠ 근데 솔직히, 이렇게 그래프알고리즘만 푸는거는...
뭔가 근심만 쌓이네요...

그래프알고리즘이 재미있긴하지만, 저가 잘 못하는
다이나믹, 구간합, 그리디, 세그먼트 관련알고리즘을 많이 풀어봐야하는데..

궁금한 부분있으시면 댓글로 질문주세요~