[백준] 16956 늑대와 양

문제

• RxC 크기의 목장이 1x1 크기로 나눠져 있고, 각 칸에는 양 또는 늑대가 있다.
  
  • 1 <= R, C <= 500
• 양은 움직이지 않고, 늑대는 인접한 칸을 이동할 수 있다.
• 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다.
  • 첫 줄에 1을 출력한 후, 해당 경우의 목장 상태를 출력한다.
  • . 빈칸 / S 양 / W 늑대 / D 울타리
• 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 이동할 수 있다면 0을 출력한다.

 

풀이

• 울타리 최소로 설치해야하는 문제가 아니다!
• 늑대와 양이 서로 붙어있지만 않으면 양을 보호할 수 있다.
  • . 을 다 D로 바꿔버리고, 늑대랑 양이 붙어있는지만 검사해줘도 된다.

# 울타리 치기 함수
def set_fence(maps, wolves):
    dx = (-1, 1, 0, 0)
    dy = (0, 0, -1, 1)
    # 각 늑대마다
    for x, y in wolves:
        # 상하좌우 이동 할 때
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            # 범위 벗어난 경우 제외
            if nx < 0 or nx >= R or ny < 0 or ny >= C:  
                continue
            # 늑대 옆 칸이 양인 경우 -> 불가능
            if maps[nx][ny] == 'S':
                return (0, maps)
    return (1, maps)

R, C = map(int, input().split())
maps = []       # 전체 목장 지도
wolves = []     # 늑대 위치
for i in range(R):
    line = list(input())
    # 늑대 위치 추가하기
    for j in range(C):
        if line[j] == 'W':      
            wolves.append((i, j))
        elif line[j] == '.':
            line[j] = 'D'
    maps.append(line)
    
possible, maps = set_fence(maps, wolves)
print(possible)     # 가능 여부
if possible :       # 가능할 때 맵 출력
    for i in range(R):
        print(''.join(maps[i]))

 

References

• 백준 16956번
• 2023.04.26 오늘의 문제