이번 문제는 BFS를 통해 해결하였다. 처음에는 한번 방문한 좌표는 다시 방문하지 않아도 될 것이라 생각하여 2차원 리스트로 방문처리를 적용하였다. 그러나 같은 좌표를 여러번 지나며 새로운 좌표에 방문하게 되는 경우가 발생한다는 것을 깨닫게 되었고, 방문처리 리스트를 3차원으로 늘려 어느 방향으로 방문했는지 여부까지 확인하도록 하여 한 좌표에 최대 4번 방문할 수 있도록 하였다. 빙판에 올라갔을 때에는 한칸씩 계속 움직이고, 멈췄을 때 범위 밖이거나 현재 좌표가 산이라면 한칸 이전 좌표로 다시 이동시켰고, 그렇지 않다면 해당 위치를 유지시키도록 하였다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
wolf = deque()
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'W':
            wolf.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def move_wolf():
    visited = [[[0 for _ in range(4)] for _ in range(m)] for _ in range(n)]
    while wolf:
        y, x = wolf.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx][i]:
                if grid[ny][nx] == '.':
                    visited[ny][nx][i] = 1
                    wolf.append((ny, nx))
                elif grid[ny][nx] == '+':
                    while 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == '+':
                        visited[ny][nx][i] = 1
                        ny, nx = ny+dy[i], nx+dx[i]
                    if not (0 <= ny < n and 0 <= nx < m) or grid[ny][nx] == '#':
                        ny, nx = ny-dy[i], nx-dx[i]
                    else:
                        visited[ny][nx][i] = 1
                    wolf.append((ny, nx))
    return visited
result = move_wolf()
for i in range(n):
    for j in range(m):
        if grid[i][j] == '.' and max(result[i][j]) == 0:
            grid[i][j] = 'P'
for i in range(n):
    print(''.join(grid[i]))