[Python/파이썬] 백준 16956번 늑대와 양

16956번: 늑대와 양

 

코드

r, c = map(int, input().split())
map_data = []
for i in range(r):
    map_data.append(list(input()))

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for i in range(r):
    for j in range(c):
        if map_data[i][j] == 'W':
            for d in range(4):
                nx = i+dx[d]
                ny = j+dy[d]
                if 0 <= nx < r and 0 <= ny < c:
                    if map_data[nx][ny] == 'S':
                        print(0)
                        exit()
                    if map_data[nx][ny] == '.':
                        map_data[nx][ny] = 'D'
print(1)
for i in range(r):
    print(*map_data[i], sep='')

 

울타리를 최소로 설치하여 늑대를 막는 것이 아니므로  풀이는 간단하다. 

늑대들의 위치를 찾아서 사방을 울타리로 둘러싸버린다. 만약 인접한 칸에 양이 있다면 울타리로 늑대를 막을 수 없기 때문에 0을 출력하고 종료시킨다.

 

사실 다 풀고 나서 다른 풀이를 찾아보니 모든 빈칸을 울타리로 바꿔주어도 되는 것 같다. 처음에 BFS, 다익스트라 이런 알고리즘도 생각해봤지만 울타리 개수 제한이 없다는 문제의 조건을 보니 딱히 알고리즘이 필요하지 않았던 문제....