[알고리즘(dovlet)] DAM(댐) 문제

링크 http://59.23.113.171/30stair/dam/dam.php?pname=dam&stair=14

댐 문제는 다음과 같다.

우선 입력으로 마을의 크기가 주어지고

기둥과 물이 지나 갈 수 있는 길이 1 과 0으로 표기된다.

그 후에 호수의 좌표가 주어지고 

댐을 건설 할 때 걸리는 시간을 주어지게 된다.

위 문제는 dfs bfs 모두 사용 가능 하다(최대 마을의 크기가 100*100 이기 때문) 

하지만 맵의 크기가 더 크게 주어진다면 bfs를 사용 시 타임 아웃에 걸리게 될 것이다.

나 같은 경우는 큐를 생성하고 큐에 첫 좌표를 주어주고 물이 이동 가능한 길을 찾아서 너비 우선 방식으로 찾아가게 만들었다.

너비 우선(BFS)의 경우 큐를 만들어야 하므로  알고리즘을 짜는데 시간이 더 걸리고 디버깅도 힘들게 된다.

하지만 쓸데없는 연산을 하지 않아 유용하다. 

해결 방법은  물의 좌표를 가지고 상하좌우 방향으로 물을 퍼트린다. 

나 같은 경우는 큐에 물에 좌표를 넣고 물이 모두 마을을 덮칠 때 까지를 구하고 그 값에 대해서 댐을 건설 할 수 있는지 체크해서 

출력하는 방법을 택하였다.

여기서는  다 찾을 필요없이 댐을 건설하는데 걸리는시간+1 까지만 구하면 최적의 방법으로 구할수있지만 나는 완전 다찾은후에 개수를 세었다.

위의 방법으로하면 수행 시간을 조금 더 단축 할 수 있을 것이다.

#include<iostream>
 
using namespace std;
 
struct _node
{
    int x, y;
    int cnt;
    _node *next;
 
};
 
struct Queue
{
    int num;
    _node *front;
    _node *rear;
 
};
 
 
void enqueue(Queue *Qu, int x, int y, int cnt)
{
    _node *NEW = new _node;
    NEW->x = x;
    NEW->y = y;
    NEW->cnt = cnt;
    NEW->next = NULL;
 
 
    if (Qu->num == 0)
    {
        Qu->front = NEW;
        Qu->rear = NEW;
 
    }
    else
    {
        Qu->rear->next = NEW;
        Qu->rear = NEW;
    }
    Qu->num++;
}
 
int dequeue(Queue *qu, int max, int map[100][100],int size)
{
    int cnt = 0;
    while (qu->num != 0)
    {
        _node *tmp = qu->front;
        int x = tmp->x;
        int y = tmp->y;
 
        if (map[x][y] == 0)
        {
            map[x][y] = tmp->cnt;
 
 
            if (x + 1 < size && map[x + 1][y] == 0)
                enqueue(qu, x + 1, y, tmp->cnt + 1);
            if (x - 1 >= 0 && map[x - 1][y] == 0)
                enqueue(qu, x - 1, y, tmp->cnt + 1);
            if (y + 1 < size && map[x][y + 1] == 0)
                enqueue(qu, x, y + 1, tmp->cnt + 1);
            if (y - 1 >= 0 && map[x][y - 1] == 0)
                enqueue(qu, x, y - 1, tmp->cnt + 1);
        }
 
        cnt = tmp->cnt;
        qu->front = qu->front->next;
        qu->num--;
        delete(tmp);
    }
    return 0;
}
 
 
 
 
 
 
 
 
int main()
{
    int size;
    cin >> size;
    int map[100][100] = { 0 };
    int last = 0;
 
 
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
                map[i][j] = 1000;
            else if (map[i][j] == 0)
                last++;
        }
    }
 
    int x, y,max;
    cin >> y >> x>>max;
 
    Queue *Qu = new Queue;
    Qu->num = 0;
    Qu->front = NULL;
    Qu->rear = NULL;
 
 
    enqueue(Qu, x-1, y-1, 1);
 
 
    dequeue(Qu, max, map, size);
    
        int c = 0;
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (map[i][j] == max+1)
                    c++;
            }
 
        }
 
 
 
        if(c!=0)
        {
        cout << c << endl;
 
 
    }
    else
    {
        cout << "OH, MY GOD" << endl;
    }
 
 
}