7793. 오! 나의 여신님

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG&categoryId=AWsBQpPqMNMDFARG&categoryType=CODE#;return%20false;

SW Expert Academy

 

우선 DFS로 풀면 스택에 쌓여 세그멘테이션 에러 발생함.

어렵다고 느낀 이유는 악마가 퍼지면서 같이 이동해야 하는데, 분명히 멈추는 것은

더 이상 이동할 곳이 없을 때 멈춰야 하지만 전체를 그렇게 짜면 악마가 퍼진 후에 큐에 쌓인 현재의 이동은 어떻게 처리 할 것인가가 문제...

 

즉 큐에서 이번 차수에 대해서만 움직이게 하는 것은 size를 통해 for문으로 진행하면 된다 .

어차피 FIFO이므로 앞의 순서대로 뽑히기 때문...

#include<iostream>
#include<queue>
using namespace std;
int N, M;

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

struct Node {
    int y;
    int x;
    int cost;
};

int main(int argc, char** argv)
{
    int test_case;
    int T;

    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> M;
        queue<Node> su;
        queue<pair<int, int> > dev;
        flag = false;
        char arr[51][51] = { 0 };

        for (int i = 0; i < N; i++)
        {
            scanf("%s", arr[i]);
            for (int j = 0; j < M; j++)
            {
                if (arr[i][j] == 'S')
                {
                    su.push({ i,j,0 });
                }

                if (arr[i][j] == '*')
                {
                    dev.push({ i,j });
                }
            }
        }


        while (!su.empty())
        {

            int size = dev.size();
            int y, x, cost;
            for (int d = 0; d < size; d++)
            {
                y = dev.front().first;
                x = dev.front().second;
                dev.pop();

                for (int i = 0; i < 4; i++)
                {
                    int newy = y + dy[i];
                    int newx = x + dx[i];

                    if (newy >= 0 && newy < N && newx >= 0 && newx < M)
                    {
                        if (arr[newy][newx] == '.' || arr[newy][newx] == 'S')
                        {
                            arr[newy][newx] = '*';
                            dev.push({ newy, newx });
                        }
                    }
                }
            }
            size = su.size();

            for (int s = 0; s < size; s++)
            {
                y = su.front().y;
                x = su.front().x;
                cost = su.front().cost;
                su.pop();

                for (int i = 0; i < 4; i++)
                {
                    int newy = y + dy[i];
                    int newx = x + dx[i];

                    if (newy >= 0 && newy < N && newx >= 0 && newx < M)
                    {
                        if (arr[newy][newx] == '.' || arr[newy][newx] == 'D')
                        {
                            if (arr[newy][newx] == '.')
                            {
                                arr[newy][newx] = 'S';
                                su.push({ newy,newx,cost + 1 });
                            }
                            else if (arr[newy][newx] == 'D')
                            {
                                cout << "#" << test_case << " " << cost + 1 << endl;
                                flag = true;
                                break;
                            }
                        }
                    }
                }
                if (flag)
                {
                    break;
                }
            }

            if (flag)
            {
                break;
            }

        }

        if (!flag)
        {
            cout << "#" << test_case << " " << "GAME OVER" << endl;
        }



    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}