백준 2589번 - 보물섬

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

육지와 바다가 각각 L과 W로 나뉘어 있다.

육지에 보물섬이 있다고 가정하고 가장 멀리 떨어져 있는 지점 두 곳이 보물섬이 있는 장소라고 할 때

두 지점의 최단 거리를 구하는 문제이다.

처음에 보물섬의 특정 위치가 정해져 있지 않아서 고민하다가

landQ라는 변수에 육지인 지점을 모두 담아서 탐색할 수 있도록 했다.

문제에 접근하는 방법은 다음과 같다.

1. 시작 지점을 설정한다.

2. 시작 지점을 기준으로 다른 육지로 갈 수 있는 모든 거리 값을 구한다.

3. 거리값을 구할 때 시작 지점과 도착 지점의 최단 거리를 구한다.

4. 시작 지점에서 다른 육지의 모든 최단 거리를 구한 후에, 구한 거리값 중에서 가장 멀리 떨어져 있는 최단 거리를 구한다.

    (보물섬이 있는 두 장소를 찾는 부분)

5. 탐색한 시작 지점 이외에 다른 육지를 시작지점으로 설정해서 위의 과정을 반복한다.

예를 들어 육지인 지점이 (1,1) / (1,3) / (2,2) / (2,4) 라고 가정해보자

이때 4지역을 모두 큐에 담아낸 다음에 while문을 4번 실행해서

각각의 육지 지점에서 다른 육지로 가는 모든 경로를 구하는 것이다.

이때 (1,1)에서 다른 육지로 가는 거리 값을 dist[y][x]로 담아낼 수 있도록 했다.

만약에 dist[y][x]의 값이 범위에 벗어나거나 한번도 방문한 적이 없다면, 이전에 갔던 거리값에서 한 시간 늘어날 수 있게 한다.

또는, 방문한 적이 있으면서 기존에 방문했을 때의 거리값보다 더 짧게 가는 경우에는 더 짧은 거리 값으로 업데이트 해줬다.

bfs로 모두 탐색을 완료한 후에 (1,1)에서 갔던 다른 지점까지의 거리값 중에서 가장 큰 값을 찾는다.

우리가 찾으려는 보물섬 사이의 거리를 ans라고 했을 때, ans와 (1,1)에서 다른 지점으로 가는 모든 경로중의 최대값을 구하면 된다.

4개의 육지 지점 중에 한 곳을 실행한 것이기 때문에 다시 dist를 0으로 초기화해준 다음에

이번에는 (1,3)을 기준으로 모든 경로를 구하면 되고 이를 마지막 지점인 (2,4)까지 실행해 주면 된다.

처음에 이 문제를 풀면서 시간 복잡도를 잘못 생각해서

시작 지점인 (y,x)와 도착 지점인 (y2,x2)를 일일히 설정한 후에 다시 bfs로 계산했더니 시간 초과가 떴다.

시작 지점을 큐에 담아낸 다음에 도착 지점을 미리 고려하지 않고

다른 모든 지점으로 가는 방향으로 문제에 접근했더니 문제를 해결할 수 있었다.

최악의 경우 모든 지점이 육지라고 가정했을 때 O(50^2)만큼 반복문을 실행해서 시작 지점의 개수 만큼 돌 수 있도록 하고

다른 모든 지점으로 가는 경로를 for문으로 4방향을 실행하면 최종적으로

O( (50^2) * (4) * (50^2) ) 이 되서 1초 이내에 간신히 통과하는 것 같다.

정점의 개수만큼 bfs가 탐색하는데 시간이 걸린다는 것을 고려하지 못해서 애초에 방향을 잘못 설정한 것이다..

이번 기회에 bfs에 대한 개념을 다시 훑어봐야겠다. 그리고 조금 더 시간을 줄일 수 있는 방향도 고려해 봐야겠다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int main() {
 
    char map[50][50]={0}; //지도
    int dist[50][50]={0}; //특정 정점 기준으로 [y][x]까지의 거리
    
    int h,w; //y,x좌표
    cin>>h>>w;
    
    queue<pair<int,int>> landQ; //출발 지점 모여있는 큐 (육지)
    
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++){
            cin>>map[i][j];
            
            //이동할 수 있는 육지
            if(map[i][j]=='L')
                landQ.push(make_pair(i,j));
        }
    
 
    int ans=0;
    while(!landQ.empty()){
        int land_y=landQ.front().first; //출발하는 y좌표
        int land_x=landQ.front().second; //출발하는 x좌표
        landQ.pop();
        
        memset(dist,0,sizeof(dist));
        
        queue<pair<int,int>> q;
        q.push(make_pair(land_y,land_x));
        
        //land_y, land_x를 기준으로 다른 육지까지 이동하는 거리 값 구하기
        while(!q.empty()){
            int y=q.front().first;
            int x=q.front().second;
            q.pop();
            
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                
                if(ny<0 || ny>=h || nx<0 || nx>=w)
                    continue;
                
                //이동할 수 없는 바다이거나 출발 지역인 land_y,land_x로 다시 올 때
                if(map[ny][nx]=='W' || (land_y==ny && land_x==nx))
                    continue;
                
                //방문한 적 없거나 방문했을 때 더 짧게 오는 경로 존재 시
                if(!dist[ny][nx] || dist[ny][nx]>dist[y][x]+1){
                    dist[ny][nx]=dist[y][x]+1;
                    q.push(make_pair(ny,nx));
                }
            }
        }
        
        //land_y,land_x를 기준으로 이동할 수 있는 최대 거리 업데이트
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                if(dist[i][j])
                    ans=max(ans,dist[i][j]);
        
    }
    
    cout<<ans<<endl;
    return 0;
}