백준: 16956 늑대와 양

문제

16956번: 늑대와 양

 

문제 풀이

 크기가 RxC인 목장이 있고, 양과 늑대가 목장 안에 있다. 울타리를 설치하여 늑대가 양에 접근할 수 없으면 1을 출력하고, 아닌 경우 0을 출력한다. 늑대가 양에 접근할 수 없는 경우는 늑대와 양이 인접해있지 않은 경우이다. 문제에서 최소 울타리 개수를 구하는 것이 아닌, 늑대가 양에 접근하지 못하도록 막으면 되므로 양을 기준으로 `상, 하, 좌, 우`로 울타리를 설치하면 문제를 해결할 수 있다.

 

코드

from sys import stdin


def visitable(x, y):
    return 0 <= x < r and 0 <= y < c


def solve():
    dirs = ((0, -1), (0, 1), (-1, 0), (1, 0))

    for x in range(r):
        for y in range(c):
            # 양인 경우
            if graph[x][y] == 'S':
                # 양의 4방향으로 탐색하여, 늑대가 있는지 확인
                for dx, dy in dirs:
                    next_x, next_y = x + dx, y + dy

                    if visitable(next_x, next_y):
                        if graph[next_x][next_y] == 'W':
                            return 0
                        elif graph[next_x][next_y] == '.':
                            graph[next_x][next_y] = 'D'
            else:
                continue
    return 1


if __name__ == '__main__':
    r, c = map(int, stdin.readline().split())
    graph = [list(stdin.readline().rstrip()) for _ in range(r)]

    if solve():
        print(1)
        for row in graph:
            print(''.join(row))
    else:
        print(0)