백준 16956번 C++ 풀이

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

16956번: 늑대와 양

시간 제한	메모리 제한	solved.ac 티어
2초	512	실버 3

문제

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

제한

• 1 ≤ R, C ≤ 500

노트

이 문제는 설치해야 하는 울타리의 최소 개수를 구하는 문제가 아니다.

---

울타리의 최소 개수를 구하는 문제가 아니라는 뜻은, 맘껏 써버려도 상관이 없다는 뜻이다. 그래서 그래프의 빈칸에 모두 울타리를 쳐버려도, 늑대가 양을 먹지만 못한다면 답이라는 뜻이다.

 

그래서 필자는 늑대가 발견되고, 늑대의 상하좌우에 양이 없다면, 늑대의 상하좌우로 울타리를 모두 쳐주고, 만약 양이 있다면 그 즉시 실패로 처리했다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int r, c;
vector<string> board;

void input() {
    cin >> r >> c;
    board.resize(r);

    for(auto& x : board) {
        cin >> x;
    }
}

void solution() {
    bool flag = true;
    int nx;
    int ny;
    int dx[4] = {0, 0, -1, 1}; // 상, 하, 좌, 우
    int dy[4] = {1, -1, 0, 0};

    for(int y = 0; y < r; y++) {
        for(int x = 0; x < c; x++) {
            if(board[y][x] == 'W') {
                for(int i = 0; i < 4; i++) {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    if(nx >= 0 && nx < c && ny >= 0 && ny < r) { // 그래프를 벗어나지 않는 좌표라면
                        if(board[ny][nx] == 'S') { // 양이 발견되면
                            flag = false; // 실패처리
                            goto END; // 반복문을 탈출한다.
                        }
                        else {
                            if (board[ny][nx] == '.') // 상하좌우에 늑대가 있으면 울타리를 치지 않는다.
                                board[ny][nx] = 'D'; 
                        }
                    }
                }
            }
        }
    }
END:
    cout << flag << endl;
    if(flag) {
        for(const auto& x : board) {
            cout << x << endl;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    input();
    solution();
}