[ BOJ ] 16956 : 늑대와 양 ( SILVER 3 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/16956)

문제

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

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

입력

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

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

출력

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

풀이 과정

늑대를 상하좌우로 가둬버린다. 만약 늑대 바로 옆에 양이 붙어있다면 0을 출력한다.

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]
row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]
done = 1
for i in range(n):
    for j in range(m):
        if maps[i][j] == 'W':
            for d in range(4):
                ny = i + row[d]
                nx = j + col[d]

                if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == '.':
                    maps[ny][nx] = 'D'
                elif 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 'S':
                    done = 0
                    break
    
    if done == 0: break

print(done)
if done == 1:
    for i in range(n): print(''.join(maps[i]))