[Baekjoon] 16956번 : 늑대와 양

1. 문제

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

• 방향 벡터 문제

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

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

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

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

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

// 제한
1 ≤ R, C ≤ 500

// 예제 입력 1
6 6
..S...
..S.W.
.S....
..W...
...W..
......

// 예제 출력 1
1
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

// 예제 입력 2
1 2
SW

// 예제 출력 2
0

// 예제 입력 3
5 5
.S...
...S.
S....
...S.
.S...

// 예제 출력 3
1
.S...
...S.
S.D..
...S.
.S...

2. 핵심 아이디어

• 최소 울타리 수와 울타리에 대한 제한조건이 없음
• 늑대나 양이 아닌 모든 곳을 울타리로 채움

3. Python 문제풀이

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
m = [list(input().rstrip()) for i in range(r)]

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
ck = False

for i in range(r) :
  for j in range(c) :
    if m[i][j] == 'W' :
      for w in range(4) :
        ii, jj = i + dx[w], j + dy[w]
        if ii < 0 or ii == r or jj < 0 or jj == c :
          continue
        if m[ii][jj] == 'S' :
          ck = True

if ck :
  print(0)
else :
  print(1)
  for i in range(r) :
    for j in range(c) :
      if m[i][j] not in 'SW' :
        m[i][j] = 'D'

for i in m :
  print(''.join(i))

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static int r,c;
  private static char[][] graph;
  private static int[] dx = {0, 0, 1, -1};
  private static int[] dy = {1, -1, 0, 0};
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());

    graph = new char[r][c];
    boolean ck = true;

    for (int i=0; i<r; i++) {
      String str = br.readLine();
      for (int j=0; j<c; j++) {
        graph[i][j] = str.charAt(j);
      }
    }

    for (int i=0; i<r; i++) {
      for (int j=0; j<c; j++) {
        if (graph[i][j] == 'W') {
          for (int xy=0; xy<4; xy++) {
            int nx = i+dx[xy];
            int ny = j+dy[xy];

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
              if (graph[nx][ny] == '.') {
                graph[nx][ny] = 'D';
              } else if (graph[nx][ny] == 'S') {
                ck = false;
                System.out.println(0);
                return;
              }
            }
          }
        }
      }
    }

    if (!ck) {
      System.out.println(0);
    } else {
      StringBuilder sb = new StringBuilder();
      System.out.println(1);
      for (int i=0; i<r; i++) {
        sb.append(graph[i]);
        sb.append("\n");
      }
      System.out.println(sb);
    }
  }
}