[백준] #16956 늑대와 양 (python)

16956번: 늑대와 양 (acmicpc.net)

16956번: 늑대와 양

 

문제

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

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

입력

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

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

출력

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

 

예제 입력 1 복사

6 6
..S...
..S.W.
.S....
..W...
...W..
......

예제 출력 1 복사

1
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

예제 입력 2 복사

1 2
SW

예제 출력 2 복사

0

 

# Code

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

graph = []

for _ in range(r):
    graph.append(list(input().rstrip()))

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))

# Comment

기본적인 bfs 문제이다. 

1. graph 라는 배열에 주어진 R x C 목장을 입력 받는다. 이때, 늑대가 양한테 갈 수 있는지 여부를 따지는 sign 변수를 False로 초기화해서 선언한다.
2. for문을 돌면서 각각 늑대, 양, '.'이 나오는 세 가지 경우를 따져준다.
(1) 늑대가 나올 경우 : 상하좌우를 체크해서 양이 있으면 sign을 True로 바꾸고 for문을 빠져나간다.
(2) 양이 나올 경우 : 아무것도 하지 않는다. continue 해서 다음으로 넘어간다.
(3) '.' 이 나올 경우 : 'D' 로 바꿔준다. (목장을 세워준다.)

문제에서 목장의 갯수는 따지지 않는다고 했기 때문에 모든 '.'을 목장으로 바꿔줘도 답안은 통과되는 것 같다.