2589번: 보물섬 [C++]

 

시간 제한          메모리 제한                     제출                              정답                          맞힌 사람              정답 비율

1 초

512 MB

32747

11772

8618

37.483%

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

 

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1 복사

8

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

2589번: 보물섬

 

흐름

시간초과된 코드(DFS)

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int m,n,visited[54][54], cnt,ey,ex,ret, result; 
char a[54][54];
vector<pair<int,int>> landList;
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

void dfs(int y, int x){
    if(cnt>=ret) return;
    if(y==ey && x == ex) {
        ret = min(ret,cnt);
    }
    for(int i=0;i<4;i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0||nx<0||ny>=m||nx>=n||visited[ny][nx]||a[ny][nx]=='W') continue;
        visited[ny][nx]=1; cnt++;
        dfs(ny,nx);
        visited[ny][nx]=0; cnt--;
    }

}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> m >> n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
            if(a[i][j]=='L') landList.push_back({i,j});
        }
    }
    //2. 육지 두 곳 고르기
    for(int i=0;i<landList.size();i++){
        for(int j=0;j<i;j++){
            cnt=0; ret=INF;
            tie(ey,ex)= landList[j];
            dfs(landList[i].first, landList[i].second);
            if(ret!=INF) result = max(result, ret);
        }
    }
    //3. 최단 거리 출력
    cout << result << "\n";
    return 0;
}

dfs로 풀었는데 시간초과가 떴다.

질문 게시판을 보니 최단거리를 구할때는 bfs를 사용해야 좋다고 했다.

dfs는 너무 많은 경로가 있기 때문이다.

 

DFS vs BFS

전에 정리한 자료

BFS는 visited[ny][nx] = visited[y][x] +1; 이기때문에 방문배열 안에 거리 정보가 저장되어있다. =>최단거리 저장됨

DFS로 최단거리를 구하면 도착지까지 간 후에 다시 처음부터 도착지까지 세야하기때문에 시간이 더 오래걸린다.

DFS는 뻗어나가는 완전탐색에, BFS는 가중치가 같은 최단거리에 사용한다.

 

 BFS 코드(틀림)

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int m,n,visited[54][54], cnt,ey,ex, result; 
char a[54][54];
vector<pair<int,int>> landList;
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};
queue<pair<int,int>> q;

void bfs(int y, int x){
    visited[y][x]=1;
    q.push({y,x});
    while(q.size()){
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || nx<0||ny>=m||nx>=n||visited[ny][nx]||a[ny][nx]=='W') continue;
            visited[ny][nx]= visited[y][x]+1;
            if(ny==ey && nx==ex) {
                return;
            }
            q.push({ny,nx});
        }
        
    }

}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> m >> n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
            if(a[i][j]=='L') landList.push_back({i,j});
        }
    }
    //2. 육지 두 곳 고르기
    for(int i=0;i<landList.size();i++){
        fill(&visited[0][0], &visited[0][0]+54*54,0);
        for(int j=0;j<i;j++){
            cnt=0;
            tie(ey,ex)= landList[j];
            bfs(landList[i].first, landList[i].second);
            result = max(result, visited[ey][ex]-1);
        }
        
    }
    //3. 최단 거리 출력
    cout << result << "\n";
     
    return 0;
}

케이스

LL

WW

일때 answer:1이다.

도착지인지 확인하기전에 visited 배열에 1을 추가하자. (답은 visited배열값-1)

 

그런데 반례 12%에서 틀렸다.

반례케이스

 

내 결과

 

왜 bfs가 잘 수행되지않았는지, dfs처럼 되었는지 궁금했다. => 선생님한테 물어봄(답변이 오면 추가할 예정)

답변

두 곳을 골라서 bfs를 하는것은 전제부터 잘못되었다.!

bfs는 출발점에서 도착점까지 최단거리를 구하는 알고리즘이므로 한 점만 필요하다!

그러므로 그냥 두 점을 고르지 말고 한 점만 골라 bfs를 수행하면 된다.

for(int i=0;i<landList.size();i++){
        fill(&visited[0][0], &visited[0][0]+54*54,0);
        tie(ey,ex)= landList[i]; 
        bfs(landList[i].first, landList[i].second);

 

 

그리고 이렇게 조합(육지 2개를 뽑음)을 사용하는 방법은 시간 초과를 발생시킨다. => 한곳을 기준으로  bfs를 수행해야한다.

2500 C 2 (2개의 육지를 골라) * 2500 (bfs로 뻗어나감) => 항상 시간복잡도를 먼저 계산하자.

 

그래서 그냥 육지마다 bfs를 수행하면 시간초과가 나지 않는다. (2500*2500)

 

또한 bfs 자체가 최단거리 알고리즘이므로, min 함수는 사용할 필요가 없고, max(최단거리중 최대) 함수를 사용해야한다.

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int m,n,visited[54][54], ret; 
char a[54][54];

const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};
queue<pair<int,int>> q;

void bfs(int y, int x){
    fill(&visited[0][0], &visited[0][0]+54*54,0);
    visited[y][x]=1;
    q.push({y,x});
    while(q.size()){
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || nx<0||ny>=m||nx>=n||visited[ny][nx]||a[ny][nx]=='W') continue;
            visited[ny][nx]= visited[y][x]+1;
            q.push({ny,nx});
            ret = max(ret, visited[ny][nx]);
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> m >> n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
        }
    }
    //2. dfs 수행
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]=='L') bfs(i,j);
        }
    }
    //3. 최단 거리 출력
    cout << ret-1 << "\n";
     
    return 0;
}

 

생각보다 간단한 문제였다. 

 

유의할 점

• 방문배열에는 최단거리값들이 저장되어있다.
  • bfs 함수 사용시에는 원소값이 최단거리이다.
  • 반복시 방문배열 초기화해야한다.
  • 방문배열 시작점은 거리 1부터 시작하므로 거리로 구한다면, 최종 거리값에 -1을 해줘야 정답이 될 수 있다.