DFS/BFS_BOJ#16956 : 늑대와 양

문제

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

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

입력

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

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

출력

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

제한

 

• 1 ≤ R, C ≤ 500

 

---

Solution

# S: 양 => 이동하지 않고 위치 이동 불가능
# W: 늑대 => 인접한 칸을 자유롭게 이동 가능
# 이 문제는 설치해야 하는 울타리의 최소 개수를 구하는 문제가 아니다.

# bfs 
# 늑대가 나올 경우 : 상하좌우를 체크해서 양이 있으면 sign을 True로 바꾸고 for문 탈출
# 양이 나올 경우 : 아무것도 하지 않는다. continue
# '.' 이 나올 경우 : 'D' 로 바꿔준다. (목장을 세워준다.)

# R, C = 목장 shape
R, C = map(int, input().split())
# 목장 그래프
graph = []
for _ in range(R):
  graph.append(list(input()))

sign = False
for i in range(R):
  for j in range(C):
    if graph[i][j] == 'W':
      dx = [-1, 1, 0, 0]
      dy = [0, 0, -1, 1]

      for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]

        # 늑대와 양이 인접해 있는 경우
        if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] == 'S':
          sign = True
          break
    
    elif graph[i][j] == 'S':
      continue

    elif graph[i][j] == ".":
      graph[i][j] = 'D'

if sign == True:
  print(0)
else:
  print(1)
  for i in graph:
    print(''.join(i))