[백준 / Python] 16956번 늑대와 양 | 초코더

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

16956번: 늑대와 양

문제

rxc크기의 목장이 주어지고, 칸은 비어있거나 양(S)또는 늑대(W)가 있다.

늑대는 상하좌우로 움직일 수 있고 늑대가 양이 있는 칸으로 이동하지 못하게 울타리를 설치하라.

 

접근법

1. 모든 좌표를 탐색

   1-1. 늑대(W)일경우,

         상하좌우를 탐색하여 인접한곳에 양이 있으면 flag 변수를 True로 변경

   1-2. 양(S)인경우,

         넘어감

   1-3. .(빈칸)인경우,

         모두 울타리로 채워줌

2. flag가 True인 경우 0을 출력

   flag가 False인 경우 1을 출력하고 maps도 출력

 

처음에 울타리를 어디에 둬야할지 굉장히 고민을 많이 했는데 다시 문제를 읽어보니 최소의 울타리수나 울타리에 대한 제한조건이 없었습니다. 그래서 양이나 늑대가 아닌 나머지 모든곳을 울타리로 채워버렸습니다.

 

전체코드

import sys

r,c=map(int,input().split())
maps=[list([p for p in sys.stdin.readline().strip()]) for _ in range(r)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
flag=False
for i in range(r):
    for j in range(c):
        #늑대
        if maps[i][j]=='W':
            for z in range(4):
                nx,ny=i+dx[z],j+dy[z]
                if nx<0 or nx>=r or ny<0 or ny>=c:
                    continue
                #양이 늑대와 인접해있으면 flag 변경
                if maps[nx][ny]=='S':
                    flag=True
                    break
        #양이면 그대로 놔둠
        elif maps[i][j]=='S':
            continue
        #.이면 모두 울타리채움
        else:
            maps[i][j]='D'

if flag:
    print(0)
else:
    print(1)
    for i in maps:
        print(''.join(i))