BOJ 2424 부산의 해적 (BOI - Baltic Olympiad in Informatics 2011)

BOJ 2424 부산의 해적

(BOI - Baltic Olympiad in Informatics 2011 Treasures and Vikings)

원본 출처: http://www.math.bas.bg/infos/files/2011-06-25-A6.pdf

먼저 BOJ문제 설명에 원본 문제에는 들어있는 Input Data 2개가 빠져있는데,

문제 설명에서 제대로 언급하지 않고 있어서 문제를 푸는데 꼭 필요한 입력값이라 생각된다.

혹시라도 맞게 푼 것 같은데, 계속 틀린다면 이 부분을 의심해 보시길.

2번째 입력데이터와 3번째 입력데이터를 보면 뭐가 문제인지 알 수 있다.

처음에 바이킹이 나 자신을 보고 있는 것은 괜찮다. (바로 도망가면 됨)

하지만 그 다음 턴부터는 바이킹이 나를 보고 있으면 나는 반드시 죽어야 한다. ㅋㅋ

뿐만 아니라 마지막 입력데이터에서 알 수 있듯이 내가 해당 턴에 보물이 있는 곳에 도착했다 하더라도,

그 턴에 바이킹 시야에 걸린다면 나는 또 보물을 획득할 수 없는 것이 되어버린다.

일단 억울한 부분은 여기까지 얘기하고, 문제 설명을 해보자~

문제를 읽어보면 '나'는 바이킹의 시야를 피해서 보물을 획득해야 한다.

그럼 처음에 드는 생각은 바이킹을 bfs 한 깊이 단위로 움직여보면서 나를 움직여 볼까? 라는 생각이 들었다.

물론... 이렇게는 풀 수 없다.

바이킹과 나 자신이 맵에서 어떻게 존재하는지를 독립적으로 들고 다닐 수가 없다.

즉, 바이킹 하나 움직이고 나 하나 움직이는 방식으로 이 문제를 푸려고 한다면, 결국 O(N^2 M^2)이 걸릴 것이다.

그럼 어떻게 할까...

먼저 첫번째 문제를 푸는 핵심은 바이킹의 시야를 기록하는 것이다.

바이킹만 가지고 맵 전체를 탐방하도록 BFS를 돌리는데,

이 때 0번째 깊이에서 바이킹이 볼 수 있는 칸에는 0을 적고

1번째 깊이에서 바이킹이 볼 수 있는 칸에는 1을 적는다.

해당칸에 이미 숫자가 적혀 있다면, 당연히 덮어쓰면 안되겠지...

아이디어가 좋다. 헤헤

이렇게 해서 바이킹 시야가 닿는 시간을 기록한 맵(이하 [바이킹시야 맵]이라 부르겠음)이 존재한다면,

내가 보물을 찾아가는 BFS코드를 작성할 때, 아까 작성한 맵에 적힌 시간과 비교만 하면서 탐색하면 될 것이다.

그런데 문제가 있다.

내가 보물을 찾아가는 BFS코드는 O(NM)밖에 안걸리지만, '바이킹시야 맵'을 만드는데는 너무 오랜 시간이 걸린다.

BFS탐색으로 노드 1개에 방문할때마다 그 노드의 가로줄과 세로줄 전체에 숫자를 채워넣어야 하므로 O(N+M)이 걸리고

BFS 자체만으로는 O(NM)이 걸릴 것이므로,

바이킹이 전체 탐색하는데 걸리는 시간복잡도는 O((N+M)NM)이 되어버린다.

N,M제한이 700이므로 1400*700*700은 6억정도 나온다.

이 방법으로는 풀 수가 없다.

여기서 쬐금 똑똑한 방법을 생각하면 된다.

물론.. 나는 여기서부터 스스로 생각해내진 못했는데,

한번 방법을 들으면 평생 까먹지 않을만한 방법이다.

바이킹시야 맵을 작성할 때,

처음에는 바이킹이 방문하는 시점만 적힌 맵을 작성한다.

0,0에서 바이킹이 처음 시작했다면,

012345

123456

234567

345678

이런 형태의 맵이 작성될 것이다.

그 다음 시야맵을 작성할건데, 결론부터 말하자면 O(4NM)시간에 바이킹시야 맵을 만들것이다.

이 맵의 이름을 lv라 하면 다음과 같은 코딩으로 만들 수 있을 것이다.

char s[701][701]; 
int lv[701][701];
queue<pair<int,int> > q;
pair<int,int> viking; //viking's coordinates
 
memset(lv,-1,sizeof(lv));
int level=0;
lv[viking.first][viking.second]=level++;
while(!q.empty()) {
    int sz = q.size(); //bfs leveling하는 스킬... 이정도는 알죠? ^-^?
    for(int z=0; z<sz; z++) {
        pii tmp = q.front(); q.pop();
        for(int i=0; i<4; i++) {
            int nx=tmp.first+dx[i],ny=tmp.second+dy[i];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(lv[nx][ny]>=0) continue;
            if(s[nx][ny]=='.') {
                lv[nx][ny]=level;
                q.push(make_pair(nx,ny));
            }
        }
    }
    level++;
}

그 다음 lv를 가지고 바이킹시야 맵을 만들어보자~

다음과 같은 정상적인 이중루프 순서 각 행의 최소값을 기록한다.

for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
        ...
    }
}

최소값이 기록된 테이블의 이름을 tm이라 하자.

문제에 나온 입력예제를 가지고 lv를 작성한다면 다음과 같이 작성될 것이다.

 6  5  4  3  2  1  0
 7  6 -1  4  3  2  1
 8  7 -1 -1 -1 -1 -1
 9  8  9 10 11 12 13
10  9 10 11 12 13 14

(I로 표시된 섬은 -1로 표기되었다.)

그리고 이를 바탕으로 tm을 만든다면 다음과 같을 것이다.

 6  5  4  3  2  1  0
 7  6 -1  4  3  2  1
 8  7 -1 -1 -1 -1 -1
 9  8  8  8  8  8  8
10  9  9  9  9  9  9

이제 위의 이중for문에서 j값만 m-1부터 0까지 거꾸로 돌려서 tm을 만들어보면 다음과 같다.

 0  0  0  0  0  0  0
 6  6 -1  1  1  1  1
 7  7 -1 -1 -1 -1 -1
 8  8  9 10 11 12 13
 9  9 10 11 12 13 14

그럼 두 tm에서 각 (x,y)에 해당하는 값의 최소값을 기록한 새로운 tm값을 만들어 보면 다음과 같다.

 0  0  0  0  0  0  0
 6  6 -1  1  1  1  1
 7  7 -1 -1 -1 -1 -1
 8  8  8  8  8  8  8
 9  9  9  9  9  9  9

이 TM값이 바이킹시야 맵이다.

위에서 언급한 이중for문을 4번 돌렸기 때문에 시간복잡도는 O(NM)이 된다.

따라서 이 바이킹시야 맵을 가지고 Y(나)가 T(보물)쪽으로 가는 bfs 탐색만 하면 답이 나오므로,

전체 시간복잡도는 O(NM)이 된다.

최종 코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
int n,m;
char s[701][701],chk[701][701];
int lv[701][701],tm[701][701];
pii na,viking,treasure;
queue<pii> q;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
const int inf = 0x3f3f3f3f;
int main() {
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++) {
        scanf("%s",s[i]);
        for(int j=0; j<m; j++) {
            if(s[i][j]=='Y') na=make_pair(i,j);
            else if(s[i][j]=='V') viking=make_pair(i,j);
            else if(s[i][j]=='T') treasure=make_pair(i,j);
        }
    }
    s[na.first][na.second]=s[viking.first][viking.second]=s[treasure.first][treasure.second]='.';
    q.push(viking);
    chk[viking.first][viking.second]=true;
 
 
    memset(lv,-1,sizeof(lv));
    int level=0;
    lv[viking.first][viking.second]=level++;
    while(!q.empty()) {
        int sz = q.size();
        for(int z=0; z<sz; z++) {
            pii tmp = q.front(); q.pop();
            for(int i=0; i<4; i++) {
                int nx=tmp.first+dx[i],ny=tmp.second+dy[i];
                if(nx<0||ny<0||nx>=n||ny>=m) continue;
                if(lv[nx][ny]>=0) continue;
                if(s[nx][ny]=='.') {
                    lv[nx][ny]=level;
                    q.push(make_pair(nx,ny));
                }
            }
        }
        level++;
    }
 
    memset(tm,0x3f,sizeof(tm));
    for(int i=0; i<n; i++) {
        int mn=inf;
        for(int j=0; j<m; j++) {
            mn = min(mn,lv[i][j]);
            if(lv[i][j]<0) {
                mn=inf;
                tm[i][j]=-1;
            } else tm[i][j]=mn;
        }
 
        mn=inf;
        for(int j=m-1; j>=0; j--) {
            mn = min(mn,lv[i][j]);
            if(lv[i][j]<0) mn=inf;
            else tm[i][j]=min(mn,tm[i][j]);
        }
    }
 
    for(int j=0; j<m; j++) {
        int mn=inf;
        for(int i=0; i<n; i++) {
            mn=min(mn,lv[i][j]);
            if(lv[i][j]<0) mn=inf;
            else tm[i][j]=min(mn,tm[i][j]);
        }
 
        mn=inf;
        for(int i=n-1; i>=0; i--) {
            mn=min(mn,lv[i][j]);
            if(lv[i][j]<0) mn=inf;
            else tm[i][j]=min(mn,tm[i][j]);
        }
    }
 
    memset(chk,false,sizeof(chk));
    q.push(na);
    chk[na.first][na.second]=true;
    level=1;
    while(!q.empty()) {
        int sz = q.size();
        for(int z=0; z<sz; z++) {
            pii tmp = q.front(); q.pop();
            if(tmp.first==treasure.first && tmp.second==treasure.second) return 0&puts("YES");
            for(int i=0; i<4; i++) {
                int nx=tmp.first+dx[i],ny=tmp.second+dy[i];
                if(nx<0||ny<0||nx>=n||ny>=m) continue;
                if(tm[nx][ny]<=level) continue;
                if(s[nx][ny]=='.') {
                    if(chk[nx][ny]) continue;
                    chk[nx][ny]=true;
                    q.push(pii(nx,ny));
                }
            }
        }
        level++;
    }
    puts("NO");
    return 0;
}