BOJ 16956 : 늑대와 양

• 문제 링크 : boj.kr/16956
• 난이도 : S3
• 태그 : 애드혹, 해 구성하기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int r, c;
    cin >> r >> c;
    vector<string> arr(r);
    for(auto &e: arr) cin >> e;

    auto check = [&](int x, int y){
        if(x < 0 || x >= r || y < 0 || y >= c) return 0;
        if(arr[x][y] == 'S') return 0;
        if(arr[x][y] == 'W') return -1;
        return 1;
    };

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

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(arr[i][j] != 'S') continue;
            for(int d = 0; d < 4; d++) {
                int x = i+dx[d];
                int y = j+dy[d];
                int ret = check(x, y);
                if(ret == 1) arr[x][y] = 'D';
                else if(ret == 0) continue;
                else {
                    cout << 0;
                    return 0;
                }
            }
        }
    }
    cout << "1\n";
    for(auto e : arr) {
        cout << e << "\n";
    }

    return 0;
}

---

풀이

양 바로 옆에 늑대가 있지 않은 이상 조건을 만족하는 것이 가능하다.

조건을 만족하는지 확인했으면, 어려울 것 없이 양 주변을 전부 둘러싸면 된다.