[ 백준, IOI 2009 Day 1 ] 곰돌이

icpc.me/5465

https://oj.uz/problem/view/IOI09_mecho

문제 요약

1초마다 현재 별들이 있는 위치에서 별들이 사방으로 퍼진다고 한다. 곰돌이는 현재 위치에서 최대한 많이 꿀을 빨아먹고 벌에 물리지 않고 집을 가고 싶어한다.

과연, 얼마나 많은 꿀을 빨아먹을 수 있을것인가? 단, 곰돌이는 1초에 S번 움직일 수 있고, 곰돌이는 현재 위치에서 상하좌우로 이동할 수 있다.

관찰

만약, T일 동안 꿀을 빨고, 출발해도 충분히 집에 도달할 수 있다고 하자. 그럼, T-n ( 0 < n <= T )일 동안 꿀을 빨고 출발하였을 때 집을 도착할 수 있을까?

너무 당연하다. 그 이유는, T일동안 꿀을 빨고 충분히 집에 도달할 수 있다는 것은 그 경로에는 벌들이 없다는 것을 의미한다. 별들은 1초마다 사방으로 퍼지는, 즉 점점 넓어지는 식으로 진행한다. 다른 의미로, 날이 작으면 작을수록 점점 좁아지는 식으로 진행한다는 것을 의미한다. 따라서, T일 이전에 도달하는 것이 가능하다.

반대로, T일 동안 꿀을 빨면 어떤 길로도 도착하지 못한다고 가정하면, 그 이상의 날에서도 진행하는 것은 불가능하다.

따라서, 우리는 T에 대한 이분탐색을 실시할 수 있다!!

그 전에, 우리는 각 칸에 대해 벌이 언제 오는지에 대한 전처리를 해 줄수 있다.

시작 벌의 위치를 큐에 넣어놓은 다음에, 4방향으로 퍼져나가는 BFS를 수행하면 된다.

이를 통해, 우리는 각 위치에 벌이 언제 오는지에 대해 알 수 있다.

여기서, 이분탐색의 범위를 결정한다.

만약, 벌이 시작점에 도달하기 이상의 시간동안 꿀을 빨아먹으면 어떻게 될까?

꿀 빨아먹다가 잡혀서 뒤지게 된다.

따라서, 우리는 이분탐색의 끝의 범위를 (벌이 시작점에 오는데 까지 걸리는 시간)-1로 정할 수 있다.

시작의 범위는 0이다. 한번도 안 빨아먹고 가야하는 수도 있다.

불쌍한 곰돌이 ㅠㅠ

이점 유의해서 곰돌이를 bfs 돌린다.

여기서, 곰돌이는 1초에 S번 움직일 수 있다고 하였다.

이걸 처리해줘야 하는데, 처리해주는 방법엔 두 가지가 있다.

1) 곰돌이의 한 걸음에 초점을 맞추는 방법

2) 시간 1초에 초점을 맞추는 방법

2)번 같은 경우엔 S번 움직일 수 있으므로 집에서 현재 위치까지의 최단 거리를 V라고 하고, T초동안 꿀을 빨아먹었으면

걸리는 시간은 T+V/S 라고 계산하는 식이다.

1)번 같은 경우엔 곰돌이가 한 번 걸을 때 1초라고 가정하는 것이다. 그러면, 벌이 한번 퍼져나가는 데에는 S초가 걸린다.

전처리를 해 줄때 S를 더해주는 식으로 진행하면 된다.

나는 1번 식으로 진행하였고,2 번 식으로 진행해도 별 무리는 없다.

이렇게 짠 코드가 밑에 있다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int pre[2000][2000];
char mark[2000][2000];
int homex,homey;
int s,sx,sy,N;
bool test(int time)
{
    bool reach[2005][2005];
    memset(reach,0,sizeof(reach));
    if(time * s >= pre[sx][sy]) return false;
    queue<piii> q;
    q.push(make_pair(make_pair(sx,sy),time*s));
    reach[sx][sy]=1;
    while(!q.empty())
    {
        int x=q.front().first.first;
        int y=q.front().first.second;
        int dis=q.front().second;
        if(mark[x][y]=='D') return true;
        q.pop();
        for(int c=0;c<4;c++)
        {
            int cx=x+dx[c],cy=y+dy[c];
            if(cx<0 || cx>=N || cy<0 || cy>=N || pre[cx][cy]<=dis+1 || mark[cx][cy]=='T' || reach[cx][cy]) continue;
            reach[cx][cy]=true;
            q.push(make_pair(make_pair(cx,cy),dis+1));
        }
    }
    return false;
}
int main()
{
    memset(pre,-1,sizeof(pre));
    scanf("%d %d",&N,&s);
    queue<pii> que;
    for(int i=0;i<N;i++)scanf("%s",mark[i]);
    for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
            {
                if(mark[i][j]=='M') sx=i,sy=j,mark[i][j]='G';
                if(mark[i][j]=='D') homex=i,homey=j;
                if(mark[i][j]=='H') que.push(make_pair(i,j)),pre[i][j]=0;
            }
    }
    pre[homex][homey]=N*N*s;
    while(!que.empty())
    {
        int x=que.front().first;
        int y=que.front().second;
        int dis=pre[x][y];
        que.pop();
        for(int c=0;c<4;c++)
        {
            int cx=x+dx[c],cy=y+dy[c];
            if(cx<0 || cx>=N || cy<0 || cy>=N || pre[cx][cy]!=-1 || mark[cx][cy]!='G') continue;
            pre[cx][cy]=dis+s;
            que.push(make_pair(cx,cy));
        }
    }
    int low=0,high=N*N*2,ans=-1;
    for(;low<high;)
    {
        int mid=(low+high)/2;
        if(test(mid)) ans=max(ans,mid),low=mid+1;
        else high=mid;
    }
    return !printf("%d",ans);
}

https://oj.uz/submission/54675