본문 바로가기

Dev/Algorithm

[백준] 3055 - 탈출

반응형

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

 

3055번: 탈출

문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치��

www.acmicpc.net

 자료구조인 Queue와 BFS(너비우선 탐색)에 대한 이해가 필요한 문제다. 물이 차오르는 것과, 고슴도치가 이동하는 것 두가지에 모두 BFS를 적용할 수 있지만 나는 별생각 없이 고슴도치의 이동에 대해서만 BFS를 적용하였고, 물이 차오르는 것은 무식하게 for문을 돌렸다. 그럼에도 pass는 나온다.

 처음엔 완전탐색으로 DFS(깊이 우선 탐색)을 해보았으나 시간초과가 나온다. 이미 갔던 곳에 대해 필터를 해서 최적화를 한다 해도 시간초과는 피할수 없는것 같다. 호기롭게 Queue도 충분히 메모리 사이즈를 잡아준 뒤 배열방식으로 잡아줬는데, 내가 생각한 그 '충분히'가 충분하지가 않았던 것 같다. 지속된 메모리 초과, 시간초과 등으로 실패를 하다가 겨우 성공했다.  

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
#include <queue>

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

typedef struct _point{
    int y;
    int x;
}point;

queue<point> points_queue;
int R, C;

void update_map(char map[51][51])
{
    char new_map[51][51];
    
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            new_map[i][j] = map[i][j];
        }
    }

    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            if (map[i][j] == '*')
            {
                for(int k=0; k<4; ++k){
                    if (new_map[i + dy[k]][j + dx[k]] == '.')
                    {
                        new_map[i + dy[k]][j + dx[k]] = '*';
                    }
                }
            }
        }
    }

    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            map[i][j] = new_map[i][j];
        }
    }
}

int main()
{
    char map[51][51];

    memset(map, 0x00, sizeof(map));
    scanf("%d%d", &R, &C);

    for (int i = 1; i <= R; ++i)
    {
        char temp[51];
        scanf("%s", temp);
        for (int j = 1; j <= C; ++j)
        {
            map[i][j] = temp[j - 1];
            if (map[i][j] == 'S')
            {
                point temp;
                temp.y = i;
                temp.x = j;
                points_queue.push(temp);
            }
        }
    }

    int ans = 0;
    while(true){
        ans += 1;

        if(points_queue.size() == 0){
            printf("KAKTUS\n");
            break;
        }

        update_map(map);
        int size = points_queue.size();
        for(int i=0; i<size; ++i){
            point pop = points_queue.front();
            points_queue.pop();
            for(int j=0; j<4; ++j){
                if (map[pop.y + dy[j]][pop.x + dx[j]] == '.'){
                    map[pop.y + dy[j]][pop.x + dx[j]] = 'S';
                    point temp;
                    temp.y = pop.y + dy[j];
                    temp.x = pop.x + dx[j];
                    points_queue.push(temp);
                }
                if (map[pop.y + dy[j]][pop.x + dx[j]] == 'D')
                {
                    printf("%d\n", ans);
                    return 0;
                }
            }
        }
    }
    return 0;
}
반응형