백준 16956. 늑대와 양 (Python)

문제

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

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

접근 방법

BFS문제이지만 나는 다른 형식으로 풀었다.
각 늑대의 좌표에서부터 4방향을 탐색하여 바로 근처에 양이 있으면 0을
그렇지 않으면 늑대 주위 모든 방향에 울타리를 만들어주었다.

울타리의 최소 개수를 구하라던지 그런 문제였다면 굉장히 까다로웠을 것 같은데
다행히 쉽게 해결할 수 있는 문제였다.

코드

def bfs(r,c):
    global ans
    for d in range(4): # 4방향 탐색
        nr = r + dir[d][0]
        nc = c + dir[d][1]
        
        # 경계선 검사
        if 0 <= nr < R and 0 <= nc < C:
        
        	# 바로 근처가 양인 경우 ans는 0
            if farm[nr][nc] == 'S':
                ans = 0
                return
                
            # 아닌 경우 주변을 모두 울타리로
            elif farm[nr][nc] == '.' or farm[nr][nc] == 'D':
                farm[nr][nc] = 'D'

# 데이터 입력받기
R, C = map(int, input().split())
farm = [list(input()) for _ in range(R)]
dir = [[-1,0],[0,1],[1,0],[0,-1]] # 4방탐색
ans = 1

for i in range(R):
    for j in range(C):
    	# 늑대가 위치한 좌표를 탐색 후 해당 좌표로 함수 실행
        if farm[i][j] == 'W':
            bfs(i,j)
            if ans == 0: # ans가 0인 경우에는 이중반복문 모두 중단
                break
    if ans == 0:
        break

# ans의 값에 따라 출력 데이터 조정
if ans == 0:
    print(ans)
else:
    print(ans)
    for f in farm:
        print(''.join(f))