💡 문제
크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.
목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.
입력
첫째 줄에 목장의 크기 R, C가 주어진다.
둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.
출력
늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.
💭 접근
이 문제는 단순히 울타리의 개수 제한없이, 최대한 설치하여 늑대가 양에게 오지 못하게만 하면 되는 문제이다.
이에 따라, 늑대가 양에게 울타리의 방해없이 양에게 도달하기 위해선 양과 인접한 칸에 있어야만 한다.
그러므로, 양과 인접하는 네 방향을 탐색하며 늑대가 있을경우 늑대를 막을 방법이 없으므로 탐색을 중단하고 바로 0을 출력하고,
인접하는 칸에 늑대가 없고 빈칸인 경우에는 울타리를 설치하며 탐색을 이어나가면 된다.
📒 코드
r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
sheep_pos = []
for i in range(r):
for j in range(c):
if graph[i][j] == 'S':
sheep_pos.append([i, j])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
safe = True
for x, y in sheep_pos:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == 'W':
safe = False
elif graph[nx][ny] == '.':
graph[nx][ny] = 'D'
if not safe:
print(0)
break
if safe:
print(1)
for i in range(r):
print(*graph[i], sep='')💭 후기
울타리의 개수 제한이 없으므로 최대한 많은 울타리를 설치하며 탐색하면 되는 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/16956
