[BOJ] 16956 늑대와 양 (Python3)

문제

크기가 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…

노트

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

문제풀이

이 예제에는 양과 늑대가 딱 분리될정도만 울타리를 쳐서 출력되게 되어있어서 이걸 어떻게 구현해야할지 아무리 고민해도 답이 안나와서 다른사람들은 어떻게 풀었나 하고 봤는데, 그냥 모든 평지를 울타리로 박아도 답으로 통과가 되서 허무했다.

어째 실버4 수준이라기엔 너무 복잡해서 어려웠는데, 양과 늑대를 제외하고 다 울타리로 막아버리게 되면 아주 단순한 기본적인 bfs풀이 문제이다.

모든 좌표를 방문하여,

* 좌표에 해당하는 문자가 W일 경우에는 bfs로 상하좌우를 확인 후, 양이 상하좌우에 있다면 반복문을 break하고 kill을 True로 바꾸고 0을 출력

* 좌표에 해당하는 문자가 S일 경우에는 continue

* 좌표에 해당하는 문자가 .일 경우에는 .을 D로 바꾸기

위 반복문이 끝나고 kill이 False라면 1과함께 리스트를 문자열로 다시 출력한다.

코드

#목장의 크기 r,c
r,c = map(int,input().split())
#목장의 상태 pasture
pasture = []
for i in range(r):
    pasture.append(list(input()))
dx = [-1,1,0,0]
dy = [0,0,1,-1]
kill = False
for i in range(r):
    for j in range(c):
        if pasture[i][j] == 'W':
            for k in range(4):
                nx = i+dx[k]
                ny = j+dy[k]
                if nx <0 or nx>=r or ny<0 or ny>=c:
                    continue
            
                if pasture[nx][ny] == 'S':
                    kill = True
                    break
        elif pasture[i][j] == 'S':
            continue
        elif pasture[i][j] == '.':
            pasture[i][j] = 'D'
if kill:
    print(0)
else:
    print(1)
    for i in range(len(pasture)):
        print("".join(pasture[i]))
               

1 2
SW
0