BOJ 16441 - 아기돼지와 늑대

문제

백준 온라인 저지 - 16441번

풀이 과정

BFS 를 이용해서 아기돼지가 안전하게 위치할 수 있는 장소들을 찾는 문제입니다.
모든 늑대들의 초기 위치를 찾은 다음, 큐에 넣고 초기화시킵니다.
이후 늑대들을 기준으로 BFS 를 수행하며 늑대들이 방문 가능한 위치를 표시합니다.
만약 늑대가 빙판을 만난다면 이동중인 방향을 기준으로 벽이나 잔디를 만날때까지 이동합니다.

코드

import sys
from collections import deque


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def preprocess():
    wolves = []

    for n in range(N):
        for m in range(M):
            if board[n][m] == 'W':
                wolves.append([n, m])

    return wolves


def in_range(x, y):
    return 0 <= x < N and 0 <= y < M


def bfs(wolves):
    visit = [[0] * M for _ in range(N)]
    q = deque(wolves)

    for sx, sy in wolves:
        visit[sx][sy] = 1

    while q:
        x, y = q.popleft()

        for direction in range(4):
            nx, ny = x + dx[direction], y + dy[direction]

            while in_range(nx, ny) and board[nx][ny] == '+':
                tx, ty = nx + dx[direction], ny + dy[direction]
                if board[tx][ty] == '+':
                    nx, ny = tx, ty
                elif board[tx][ty] in ['W', '.']:
                    nx, ny = tx, ty
                    break
                else:
                    break

            if in_range(nx, ny) and not visit[nx][ny] and board[nx][ny] != '#':
                visit[nx][ny] = 1
                q.append([nx, ny])

    return visit


def solution():
    wolves = preprocess()
    wolves_visits = bfs(wolves)

    answer = [['.'] * M for _ in range(N)]
    for n in range(N):
        for m in range(M):
            if not wolves_visits[n][m] and board[n][m] == '.':
                answer[n][m] = 'P'
            else:
                answer[n][m] = board[n][m]

    for n in range(N):
        print(''.join(map(str, answer[n])))


if __name__ == '__main__':
    N, M = list(map(int, sys.stdin.readline().split()))
    board = [list(sys.stdin.readline().strip()) for _ in range(N)]

    solution()