백준 16956 늑대와 양 c++ dfs, bfs

 

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

16956번: 늑대와 양

 

예시 출력 때문에 헷갈렸으나,

 

울타리를 쳐서 늑대와 양이 만나지 못하게 하는 것이 가능하면 1, 불가능하면 0을 출력하는 문제였다.

 

그 아래 N X N map은 'D'가 어느 위치에 있던지 상관없이 1과 0만 잘 출력되면 통과한다. (예시에 대한 출력이 달라질 수 있음을 알려줬으면 더 쉽게 풀었을 것 같다.)

 

단순히 0과 1을 출력하기 위해서는 양의 상하좌우에 늑대가 있는지만 확인하면 된다. (울타리 수의 제한은 없고, 양과 늑대 사이에 공간이 있다면 울타리를 칠 수 있기에)

 

나는 map도 잘 출력해야 하는줄 알고 DFS, BFS를 이용해서 'D'를 잘 표시해주었다..

 

 

 

1. DFS

 

처음에는 DFS를 진행하며 해당 좌표의 상하좌우를 확인하는 방식으로 풀었다. 

 

#include <iostream>

using namespace std;

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

char Map[500][500];
char checkMap[500][500];

int RR;
int CC;

void DFS(int y, int x)
{
    bool checkD = false;
    int newy;
    int newx;

    checkMap[y][x] = 1;

    for(int i = 0; i < 4; i++) { //상하좌우확인

        newy = y + dy[i];
        newx = x + dx[i];

        if (newy < 0 || newy >= RR || newx < 0 || newx >= CC || checkMap[newy][newx] == 1)
            continue;
        if (Map[newy][newx] == 'S') //sheep을 만났다면
        {
            if (Map[y][x] == '.') { //본인이 '.' 라면 'D'를
                Map[y][x] = 'D';
                checkD = true;
                break;
            }
            else
            {
                cout << 0; //본인이 늑대라면 0 출력 후 프로그램 종료 .. 이 부분은 잘못된 코드 같다.
                exit(0);
            }
        }
    }
    if (checkD)
        return;

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

        if (newy < 0 || newy >= RR || newx < 0 || newx >= CC || checkMap[newy][newx] == 1 || Map[newy][newx] == 'D')
            continue; //누가 갔던 곳(heckMap[newy][newx] == 1)이거나 울타리( Map[newy][newx] == 'D') 면 안간다. 아니라면 DFS
        DFS (newy, newx);
    }
}


int main() {

    int R, C;
    cin >> R >> C;
    RR = R;
    CC = C;

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> Map[i][j];
        }
    }

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (Map[i][j] == 'W') //W 일때, DFS 들어가기
                DFS(i, j);
        }
    }
    cout << 1 << endl;
    
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << Map[i][j];
        }
        cout<< endl;
    }
    
    return 0;
}

 

2. BFS

 

스터디에서 코드 리뷰를 받은 결과 다른 팀원분이 Input 제한이 적었기에 DFS도 가능했지만,

N의 값이 컸다면 DFS가 시간 초과를 낼 수 있을 거라는 의견을 받았다.

 

시간 복잡도를 줄이기 위해 BFS로 변경했다.

#include <iostream>
#include <queue>

using namespace std;

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

char Map[500][500];
int checkMap[500][500];

queue<pair<int, int>> Q;

int RR;
int CC;
/*
void DFS(int y, int x)
{
    bool checkD = false;
    int newy;
    int newx;

    checkMap[y][x] = 1;

    for(int i = 0; i < 4; i++) {

        newy = y + dy[i];
        newx = x + dx[i];

        if (newy < 0 || newy >= RR || newx < 0 || newx >= CC || checkMap[newy][newx] == 1)
            continue;
        if (Map[newy][newx] == 'S')
        {
            if (Map[y][x] == '.') {
                Map[y][x] = 'D';
                checkD = true;
                break;
            }
            else
            {
                cout << 0;
                exit(0);
            }
        }
    }

    if (checkD)
        return;

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

        if (newy < 0 || newy >= RR || newx < 0 || newx >= CC || checkMap[newy][newx] == 1 || Map[newy][newx] == 'D')
            continue;
        DFS (newy, newx);
    }
}
*/

int BFS (int y, int x)
{
    int tmpy;
    int tmpx;
    int nexty;
    int nextx;
    bool isD;

    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        tmpy = Q.front().first;
        tmpx = Q.front().second;
        isD = false;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            nexty = tmpy + dy[i];
            nextx = tmpx + dx[i];

            if (nexty < 0 || nexty >= RR || nextx < 0 || nextx >= CC || checkMap[nexty][nextx] == 1 || Map[nexty][nextx] == 'D')
                continue;
            if (Map[nexty][nextx] == 'S') { //sheep을 만났을 때
                if (Map[tmpy][tmpx] == 'W') //내 자신이 울프라면... return 0
                    return 0;
                else
                {
                    Map[tmpy][tmpx] = 'D'; //내 자신이 '.' 였다면 'D'로 바꿔주기
                    isD = true;
                    break;
                }
            }
        } //상하좌우에 하나라도 sheep이 있으면 D로 남아야 하기 때문에, push하기 전에 sheep을 찾는다.

        if (isD)
            continue; //현재 좌표가 D로 바뀌는 곳이라면, 따로 상하좌우를 push 하지 않는다.

        for (int i = 0; i < 4; i++) {
            nexty = tmpy + dy[i];
            nextx = tmpx + dx[i];

            if (nexty < 0 || nexty >= RR || nextx < 0 || nextx >= CC || checkMap[nexty][nextx] == 1 || Map[nexty][nextx] == 'D')
                continue;
            Q.push(make_pair(nexty, nextx));
            checkMap[nexty][nextx] = 1; //이 부분을 꼭 for 문 안에서 해주기
        }
    }
    return 1;
}

int main() {

    int R, C;
    cin >> R >> C;
    RR = R;
    CC = C;

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> Map[i][j];
        }
    }

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (Map[i][j] == 'W') {
                if(checkMap[i][j] != 1) { // 이미 다른 wolf에 의해 체크된 곳이라면 굳이 들어가지 않음
                    checkMap[i][j] = 1;
                    if (!BFS(i, j)) { // return 0이 되는 경우 (늑대랑 양이 바로 붙어있는)
                        cout << 0 << endl;
                        return 0;
                    }
                }
            }
        }
    }

    cout << 1 << endl;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << Map[i][j];
        }
        cout<< endl;
    }
    return 0;
}

 

DFS는 익숙하지만 BFS는 익숙하지 않아서, 메모리 초과를 겪었다.

위에 *이 부분을 꼭 for문에서 해주기*에서,

이미 갔던 곳임을 표시해주는 checkmap을 for문에서 바로 해주지 않고,

while문 시작 부분에서 Queue를 꺼내면서 check 해주게 되면, 예외처리를 한다고 하더라도 동일한 좌표를 Queue안에 많이 넣게 되어 size가 커져 메모리 초과를 낸다.

비슷한 BFS 문제에서도 겪은 현상으로, for문에서 다음으로 넘어갈 좌표에 해당하는 checkMap을 바로바로 해줘야 한다.

 

 

BFS를 하더라도, 다음 좌표를 큐에 담기 전에 상하좌우 확인하여 자신이 'D'인지를 확인해야 한다고 생각했다.

그러면서도, 비슷한 for문을 2번 사용했기 때문에 더 효율적인 방법은 없을까 하는 생각이 들었다.