[SWEA] 9236 곰돌이

출처: SWEA

Approach

① Input Data를 입력 받아 base[][]에 저장한다.

    벌(bee)과 곰돌이(bear) 이동을 확인하기 위해 BFS를 여러번 해야 하는데

    이를 위해 base[][]를 원본으로 활용

    - 곰돌이 위치(M), 집 위치(D), 벌의 초기 위치(H)를 표시한다.

② 벌들을 확산시킨다.

    확산되는 원리는 BFS 방식을 이용한다.

▶ BFS (Breadth-First Search, 너비 우선 탐색) 

BFS (Breadth-First Search, 너비 우선 탐색)

 

곰돌이가 lev 초 이동 했을 때, 벌들가 마주치는지 여부를 판단할 때,

→ 곰돌이가 T초동안 움직이고 벌들이 T초내로 확산했을 때 마주치는지 확인 ( X )

→ bee[][]에 벌들이 확산되는 시간 T초를 lev 변수로 표시해서, 

    곰돌이가 T초에 그곳을 피해갈 수 있는지 확인 ( O )

 

벌(H)들이 T초 동안 이동되는 지점은 아래와 같다.

- 곰돌이가 처음 위치한 (M)에 4초에 도달한다.

③ 벌들의 확산되는 시기를 bee[][]에 표현하였다면

    곰돌이를 1~T 초까지 특정 시점을 정해서 집으로 돌아갈 수 있는지 BFS 탐색한다.

    이때, 1 → 2 → 3 → 4 → ...  → T 식으로 하면 TLE가 발생한다.

    이분탐색 중 Upper Bound를 활용해서 특정 시점 탐색 시간을 줄인다.

▶ Binary Search (이분 탐색)  

Binary Search (이분 탐색)

▶ Parametric Search  

[탐색] Parametric Search

---

#include <stdio.h>

#define EMPTY (0x1fffffff)
#define IMPOSSIBLE -1

const int MAX_N = 800 + 2;
const int MAX_S = 1e3 + 2;
const int MAX_Q = MAX_S * MAX_S * 4;
const int dx[4] = { 0, -1, 1,  0 };
const int dy[4] = { 1,  0, 0, -1 };

struct Node
{
    int x, y;
};

struct Queue
{
    Node arr[MAX_Q + 1];
    int fr, re, sz;
    void init()
    {
        fr = re = sz = 0;
    }
    void push(Node data)
    {
        arr[re++] = data;
        re %= MAX_Q;
        sz++;
    }
    void pop()
    {
        fr = (++fr) % MAX_Q;
        sz--;
    }
    Node top()
    {
        return arr[fr];
    }
    bool isEmpty()
    {
        return sz == 0 ? true : false;
    }
}que;

int bearX, bearY, homeX, homeY;
int N, S, TC, lev, ans;
char base[MAX_N][MAX_N], map[MAX_N][MAX_N];
int bee[MAX_N][MAX_N];

void init()
{
    ans = IMPOSSIBLE;
    que.init();
}

void input()
{
    scanf("%d %d", &N, &S);
    for (int i = 1; i <= N; i++) {
        scanf("%s", &(base[i][1]));
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (base[i][j] == 'M') // 곰돌이 위치
                bearX = i, bearY = j;
            else if (base[i][j] == 'D') // 집 위치
                homeX = i, homeY = j;
            else if (base[i][j] == 'H') // 벌
                que.push({ i,j });
            // 벌(bee) 표시
            if (base[i][j] == 'H')
                bee[i][j] = 0;
            else
                bee[i][j] = EMPTY;
        }
    }
}

void initMap()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            map[i][j] = base[i][j];
        }
    }       
}

void beeMove()
{
    lev = 0;
    while (!que.isEmpty())
    {
        lev++;
        // 현재 담겨 있는 Queue크기 만큼
        int queSize = que.sz;
        while (queSize--)
        {
            Node top = que.top(); que.pop();
            for (int d = 0; d < 4; ++d)
            {
                int nextX = top.x + dx[d];
                int nextY = top.y + dy[d];
                if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > N)
                    continue;
                // 최초로 곰이 있었던 곳이거나 풀밭인 곳
                if (map[nextX][nextY] == 'M' || map[nextX][nextY] == 'G')
                {
                    // 다녀간 지점 표시
                    map[nextX][nextY] = 'H';
                    // 다녀간 시점 표시
                    bee[nextX][nextY] = lev;
                    que.push({ nextX,nextY });
                }
            }
        }
    }
}

bool isPossible(int lev)
{
    Node cur = que.top();
    if (bee[cur.x][cur.y] <= lev)
        return false;
    while (!que.isEmpty())
    {
        for (int i = 0; i < S; i++)
        {
            int queueSize = que.sz;
            while (queueSize--)
            {
                cur = que.top(); que.pop();
                // 벌이 이미 있는 곳인 경우
                if (bee[cur.x][cur.y] <= lev)
                    continue;
                for (int k = 0; k < 4; k++)
                {
                    int nextX = cur.x + dx[k];
                    int nextY = cur.y + dy[k];
                    if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > N)
                        continue;
                    // 곰돌이가 집에 도착한 경우
                    if (nextX == homeX && nextY == homeY)
                        return true;
                    // 풀밭이면서 아직 벌들이 확산되지 않은 곳인 경우
                    // 곰돌이가 아직 이동하지 않은 곳(!= M) (중복 방문 X)
                    if (map[nextX][nextY] == 'G' && bee[nextX][nextY] > lev)
                    {
                        que.push({ nextX, nextY });
                        map[nextX][nextY] = 'M';
                    }
                }
            }
        }
        lev++;
    }
    return false;
}

void upperbound()
{
    int start = 0, end = N * N;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        que.init();
        que.push({ bearX,bearY });
        initMap();
        if (isPossible(mid)) {
            ans = mid;
            start = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for(int tc = 1; tc <= TC; ++tc)
    {
        init();
        input(); // BFS 하기좋게 base[][] Setup
        initMap(); // 입력받은 base[][]를 map[][]에 반영          
        beeMove(); // 벌 퍼뜨리기
        upperbound(); // 곰돌이가 움직일 수 있는 시간대를 이분탐색
        printf("#%d %d\n", tc, ans);
    }
    return 0;
}