[baekjoon] 백준 16956번(파이썬): 늑대와 양

문제

16956번: 늑대와 양

- 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다.

- 각각의 칸에는 비어있거나, 양 또는 늑대가 있다.

- 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다.

- 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

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

- 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

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

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

- 늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다.

- 울타리는 'D'로 출력한다.

- 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

알고리즘

- 문제를 잘 읽어보면 힌트가 있다.

- 울타리의 개수에 대한 내용이 없고 예제 3번과 같은 경우도 보면 양이 없는 반면에 울타리를 가운데에 설치한 것을 확인할 수 있다.

- 이러한 힌트를 보았을 때 울타리를 무한히 사용하여 늑대와 양 사이에 설치하면 된다.

- 양의 위치에서 좌/우/위/아래 방향에 늑대가 있는지 확인하고 늑대가 있으면 울타리로 해결하지 못하므로 0을 출력한다.

 - 그게 아니라면 1을 출력하고 모든 빈칸에 울타리를 설치하여 2차원 리스트를 출력하면 된다.

코드

import sys

r, c = map(int, sys.stdin.readline().split())

# 2차원 리스트의 맵 정보 입력 받는다.
graph = []
for _ in range(r):
    graph.append(list(map(str, input())))

# 좌/우/위/아래 방향 이동
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 늑내가 양이 있는 칸으로 갈 수 있으면 True,
# 아니라면 False
boolean = False

# 2차원 리스트를 양이 있는 곳 좌/우/위/아래에 늑대가 있는지 확인
for i in range(r):
    for j in range(c):
        if graph[i][j] == "W":
            for k in range(4):
                x = i + dx[k]
                y = j + dy[k]

                # 2차원 리스트 범위를 벗어나면 넘긴다.
                if x <= -1 or x >= r or y <= -1 or y >= c:
                    continue

                # 늑대가 있으면 반복문을 멈추고 0을 출력
                if graph[x][y] == "S":
                    boolean = True
                    break

if boolean:
    print(0)
else:
    print(1)
    # 늑대와 양이 있는 위치를 제외하고 모두 울타리 설치
    for i in range(r):
        for j in range(c):
            if graph[i][j] == '.':
                graph[i][j] = "D"
    for k in graph:
        print(''.join(k))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법