[Python] 16956번 늑대와 양

16956번: 늑대와 양 (acmicpc.net)

16956번: 늑대와 양

---

 

22/09/03

 

 

그룹 연습 중 풀었던 문제이다.

 

그래프 문제임에도 불구하고, 재치 있는 아이디어로 쉽게 풀 수 있는 문제여서 즐겁게 풀었었다.

---

 

문제 접근 방식:

 

 

먼저 가능한 경우와 불가능한 경우를 따지는 것이 우선이라고 생각하였다.

 

가능한 경우라면, 울타리를 칠 때, 빈 들판에다 모두 울타리를 쳐버리면 양도 늑대도 모두 못 움직이니깐 늑대가 양을 잡아먹지 못하도록 만들 수 있을 것이라고 생각했다.

 

어차피 이 문제는 힌트에서도 나와있듯이 울타리의 최소 갯수를 구하는 문제도 아니고, 울타리를 최소한으로 사용하여 그래프를 구성하라는 말 또한 없었기 때문에 울타리를 얼마큼 사용하든지 상관없기 때문이다.

 

불가능한 경우를 곰곰히 생각해보니, 양과 늑대가 붙어있다면 불가능할 것이라고 생각했다.

 

울타리로 모두 가둬도 바로 옆으로 가서 잡아 먹을 수 있기 때문이다.

 

따라서 그래프의 원소를 모두 반복하여 돌면서 늑대인 경우 4방향에 양이 붙어있는지 확인하는 코드를 짜주었다.

 

만약 양이 붙어있으면 불가능을 출력하고, 모든 늑대에 대해서 양이 붙어있지 않다면 빈 들판 대신에 울타리를 출력하도록 코드를 짜주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16956번 늑대와 양
import sys
input = sys.stdin.readline

R, C = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(R)]

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def main():
    for row in range(R):
        for col in range(C):
            if graph[row][col] == 'W':
                for r, c in zip(dr, dc):
                    nr, nc = row+r, col+c
                    if 0 <= nr < R and 0 <= nc < C:
                        k = graph[nr][nc]
                        if k == 'S':
                            print(0)
                            return
    print(1)
    for row in range(R):
        for col in range(C):
            if graph[row][col] == '.':
                print('D', end = '')
            else:
                print(graph[row][col], end = '')
        print()
main()