[백준 알고리즘] 백준 16956번 늑대와 양 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 16956번 늑대와 양 파이썬(Python)

1) 문제번호 : 16956번

 

2) 문제 출처

https://www.acmicpc.net/problem/16956

16956번: 늑대와 양

 

2. 문제

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

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

 

3. 제약사항

 

 

4. 입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

 

5. 출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

 

6. 풀이

- 늑대가 있다면 양한테 갈 수 있으면 sign을 True로 두고, sign의 T/F 에 따라 출력을 한다.

 

7. 소스 코드

import sys
input=sys.stdin.readline

R, C = map(int, input().split()) # 목장의 크기

board = [] # 목장

# 목장 입력
for _ in range(R) :
    board.append(list(input().rstrip()))

sign = False # 늑대가 양한테 갈 수 있는지
for i in range(R) :
    for j in range(C) :
        # 늑대일 경우
        if board[i][j] == "W" :
            dx = [-1, 1, 0, 0]  # 상, 하, 좌, 우
            dy = [0, 0, -1, 1]  # 상, 하, 좌, 우

            for k in range(4) :
                nx = i + dx[k]
                ny = j + dy[k]

                if 0<=nx<R and 0<=ny<C and board[nx][ny]=="S":
                        sign = True
                        break
        # 양일 경우
        elif board[i][j] == "S" :
            continue

        # 빈칸일 경우
        elif board[i][j] == "." :
            board[i][j] = "D"

if sign :
    print(0)

else :
    print(1)
    for i in board :
        print(''.join(i))

 

---