[C++] 백준 16956 늑대와 양

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

16956번: 늑대와 양

 

1. 서론

 

BFS 문제란다. 문제에 자세한 조건이 안 쓰여 있어서 어떻게 풀어야 하는지 감이 안 왔는데 그냥 자유롭게 풀면 되는 문제였다.

 

2. 문제 풀이

 

RxC 크기의 배열이 주어진다. 배열에 S는 양이 있는 위치를 W는 늑대가 있는 위치를 알려준다. 그 외의 빈 곳은 '.'으로 표시한다.

이때 양의 위치는 고정되어 있고 늑대는 움직일 수가 있는데 양과 늑대를 만나지 않기 하기 위해 울타리를 설치하려고 한다.

이때 울타리는 D라고 표시한다. 이때 울타리를 설치해서 막을 수 있으면 1을 출력하고 울타리를 설치한 배열을 출력하고 막을 수 없다면 0을 출력한다.

 

주어진 조건이 이것 밖에 없었기 때문에 어떻게 풀어야 할지 감이 안 왔다. 예시를 보고 이걸 어떻게 풀어야 하나 생각했다.

웉타리를 정확히 어디에다가 설치해야 하는 기준이 없었기 때문이다. 밑에 설치해야 하는 울타리의 개수가 꼭 최소가 아니어도 된다고 쓰여있었지만 뭔가 울타리를 적절히 설치했다는 걸 평가하는 알고리즘이 있을 것 같았다. 그 기준을 모르겠어서 고민하다가 포기하고 인터넷에서 풀이 방법을 찾아봤다.

 

결과적을 말하자면 그런 기준이 없다는게 결론이다. 말 그대로 자유롭게 해도 된다. 

물론 내부에 정말 양에게 갈 수 있나 없나를 평가하는 알고리즘은 있을 것이지만 울타리를 어디에 놓을지, 몇 개를 놓을지는 마음대로 해도 된다는 것이다. 그래서 배열에서 양이 발견되면 양의 상하좌우에 늑대가 있는지 찾아본다. 그리고 늑대가 있다면 0을 출력하고 끝내고, 없다면 상하좌우에 그냥 울타리를 설치해서 틀어막아줬다. 최소와 효율과는 거리가 멀지만 어떻게 해야 할지를 모르겠어서... ㅎ

 

3. 코드 설명

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int r, c, i, j, k, f = 1;
    string s;
    vector<string> v;
    int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};

    cin >> r >> c;

    for (i = 0; i < r; i++)
    {
        cin >> s;
        v.push_back(s);
    }

    for (i = 0; i < r; i++)
    {
        for (j = 0; j < c; j++)
        {
            if (v[i][j] == 'S')
            {
                for (k = 0; k < 4; k++)
                {
                    if (i + dx[k] >= 0 && j + dy[k] >= 0 && i + dx[k] < r && j + dy[k] < c)
                    {
                        if (v[i + dx[k]][j + dy[k]] == 'W')
                        {
                            f = 0;
                            cout << f << endl;
                            return 0;
                        }
                        else if (v[i + dx[k]][j + dy[k]] == '.')
                            v[i + dx[k]][j + dy[k]] = 'D';
                    }    
                }
            }
        }
    }

    cout << f << endl;

    for (i = 0; i < r; i++)
        cout << v[i] << endl;
}

 

dx, dy는 상하좌우를 위한 배열이다. 모아두면 (0, 1) (-1, 0) (0, -1) (1,0) 이렇게 상하좌우를 한바퀴 돌 수 있게 된다.

한 줄을 하나의 문자열로 입력받고 그걸 벡터로 모아 문자열 배열을 만들었다. (사실 그냥 문자형 배열로도 만들어봤는데 메모리는 줄어드는데 실행시간이 오히려 늘어났다)

반복문을 돌리면서 양의 위치를 확인한다. 양이 발견되면 dx, dy를 이용해 상하좌우에 양이 있는지 확인한다. 이때 -1, +1 이 포함되어 있기 때문에 범위를 넘지 않도록 꼭 막아줘야 한다. 바로 상하좌우에 이미 늑대가 와있으면 울타리를 설치할 수 없으므로 0을 출력하고 프로그램을 끝내줬다. (더 이상 프로그램을 돌릴 필요가 없기 때문에)

늑대가 상하좌우에 없는 경우에 만약 상하좌우가 빈칸이라면 그 값을 D로 바꾸어 울타리를 설치해준다.

그리고 모든 배열을 다 탐색하고 나면 값들을 출력해준다.

근데... BFS.... 이렇게 하는거 아닐 텐데 ㅎ