백준, BOJ, 2589번, 보물섬 : C++ [CPP] ★★

조금 특이한 BFS랄까..?

최장거리의 최단시간을 구해야 한다.

???? 처음에는 이해가 안갔다.

 

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

 

 

---

 

#맞는 풀이

#include <bits/stdc++.h>

using namespace std;

int row, col; //행, 열

char arr[50][50]; //입력
int visited[50][50]; //방문여부 -1로 초기화
int memo[50][50]; // 기억

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int main(){
    cin >> row >> col;
    
    //문자열로 입력받음.
    for(int i = 0; i<row; i++){
        string s;
        cin >> s;
        //visited -1 초기화
        for(int j = 0; j<col; j++){
            arr[i][j] = s[j];
            visited[i][j] = -1;
        }
    }
    //큐 생성
    queue<pair<int,int>> q;
    
    for(int i = 0; i<row; i++){
        for(int j = 0; j<col; j++){
            //L이라면 시작노드 가능.
            if(arr[i][j] == 'L'){
                q.push({i,j});
                visited[i][j] = 0; //시작
                int Mx = -1; //해당 노드에서 가장 먼 시간 저장
                while(!q.empty()){
                    auto cur = q.front();
                    q.pop();
                    for(int dir = 0; dir<4; dir++){
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];
                        //범위, 방문, 바다가 아니면 방문 가능
                        if(nx<0 || nx>=row || ny<0 || ny>=col)continue;
                        if(visited[nx][ny] != -1 )continue;
                        if(arr[nx][ny] == 'W')continue;
                        
                        visited[nx][ny] = visited[cur.first][cur.second] + 1;
                        q.push({nx,ny});
                        
                        //해당 시작노드부터 가장 먼 곳의 값 저장
                        Mx = max(Mx, visited[nx][ny]);
                    }
                }
                //해당 노드(시작노드, (i,j))로 부터 가장 먼 값 저장.
                memo[i][j] = Mx;
                //visited초기화 -> 모든 노드에 대해서 조사해야함. (BruteForce)
                // -> 2500개의 칸을 2500번 조사. -> 6,250,00 밖에 안됨.
                for(int i = 0; i<row; i++){
                    for(int j = 0; j<col; j++){
                        visited[i][j] = -1;
                    }
                }
            }
        }
    }
    
    int ans = 0;
    
    for(int i = 0; i<row; i++){
        for(int j = 0; j<col; j++){
            ans = max(ans, memo[i][j]);
        }
    }
    
    //가장 먼거리에 대한 최단시간 출력
    
    cout << ans;
    

    return 0;
}

 

최장거리를 구하기 위해서는 BFS로도 소용이 없다.

DFS로도 최장거리는 소용이 없다.

즉, 한 번의 탐색으로 최장거리를 발견할 수 없다는 말이다.

-> 그래서 BruteForce가 필요했다.