Sign in Subscribe
PS

[PS] BOJ 16956 / 늑대와 양

Minjun Kim

• 2 min read
[PS] BOJ 16956 / 늑대와 양
Thumbnail: Photo by Den Cops (Unsplash)
문제 링크: https://www.acmicpc.net/problem/16956

그래프 탐색으로 푸는 간단한 문제입니다.

풀이

아이디어

이 문제는 스페셜 저지 문제이며, 울타리를 최소한으로 설치해야 하는 문제가 아닙니다. 오로지 울타리를 적절히 배치해 늑대와 양이 만나지 못하게 할 수 있는지 판단하는 문제이니, 단순히 빈 칸을 전부 울타리로 바꾸는 방법을 생각했습니다.

  1. 입력을 받으면서, 빈 칸(.)을 전부 울타리(D)로 바꿔서 저장합니다.
  2. 1에서 만든 맵 배열에서, 모든 늑대의 위치에서 그래프 탐색을 진행해 양을 만날 수 있는지 확인합니다.
  3. 양을 만날 수 있다면 0을, 만날 수 없다면 1과 1에서 만든 맵 배열의 내용을 출력해줍니다.

전체 코드

input = open(0).readline
R, C = map(int, input().split())
Map = [list(map(lambda s: "D" if s == "." else s, input().rstrip())) for _ in range(R)]

visited = [[False for _ in range(C)] for _ in range(R)]
diff = ((-1, 0), (1, 0), (0, 1), (0, -1))
wolf_can_meet = False

def dfs(r, c):
    for dr, dc in diff:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and Map[nr][nc] != "D":
            visited[nr][nc] = True
            if Map[nr][nc] == "S":
                return True
            
            if dfs(nr, nc):
                return True

for r in range(R):
    for c in range(C):
        if Map[r][c] == "W" and not visited[r][c]:
            wolf_can_meet = dfs(r, c)
        if wolf_can_meet:
            break
    if wolf_can_meet:
        break

if wolf_can_meet:
    print("0")
else:
    print("1")
    print("\n".join("".join(row) for row in Map))

solution.py