백준 16956 _ Python

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

16956번: 늑대와 양

문제

---

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

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

 

 

입력

---

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

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

 

출력

---

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

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

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

 

접근법

---

1. 단순 BFS 문제이다 . 문제 조건에서 울타리를 최소로 놓는다 하면, 조금 더 생각해봐야 하지만, 그것이 아니니
2. 그냥 모조리 울타리를 세워준다. 또한 양 옆자리에 늑대가 있으면 바로 끝낸다.
3. 만약 늑대가 양에 접근하지 못한다면, 빈 공간(".") 을 울타리로 치환하여 print 해준다.

 

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

n,m = map(int,input().split())
a=[input() for _ in range(n)]
# 입력을 마치고, possible 을 True 라 해놓고 , 각 공간마다 돌면서, 양 바로 옆에
# 늑대가 있는지 봐준다. 

possible = True
for i in range(n):
    for j in range(m):
        if a[i][j]=='S':
            for k in range(4):
                nx = i+dx[k]
                ny = j+dy[k]
                if 0<=nx<n and 0<=ny<m:
                    if a[nx][ny]=='W':
                        possible=False

if not possible : print(0)
else:
    print(1)
    for i in range(n):
        for j in range(m):
            if a[i][j]=='.':
                print('D',end='')
            else:
                print(a[i][j],end='')
        print()