BOJ 16441 아기돼지와 늑대(Python 3)

https://www.acmicpc.net/problem/16441

이 문제에서 어려운 부분이 늑대가 빙판길에서 이동하는 방법과 중복 확인을 하는 방법을 처리하는 것인데, 나는 중복 체크 때문에 애를 좀 먹었다.

초원은 일반 상하좌우 BFS를 이용해 구현하였고, 빙판에 있을 때는 while문을 이용해 늑대를 계속 이동시키다가 맵의 범위를 넘어가거나, 산에 있을 때 값을 한번 빼서 바로 전에 이동한 값을 방문한 것으로 만들고, 빙판길을 가다가 초원이 나왔을 경우 바로 while 문을 빠져나와서 초원을 방문한 것으로 만들었다.

이러면 빙판이 교차할 때 늑대가 갑자기 멈춰버리는 일도 없으니 문제를 해결 할 수 있을 것이다.

필자는 질문 글에 있는 반례도 맞던데, 제출하면 틀렸다고 나와서 머리 싸매다가 반례를 하나 찾아냈다.

혹시 여기까지만 보고 코드를 만드는 분이 있을까봐 반례도 하나 같이 올린다.

반례확인

10 7
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#.#+#.#
#######

답
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#P#+#P#
#######

코드확인

from collections import deque
n,m=map(int,input().split())
D=[list(map(str,[*input()])) for _ in range(n)]
v=[[0]*m for _ in range(n)]
dx,dy=[0,0,-1,1],[1,-1,0,0]
q=deque()
for i in range(n):
    for j in range(m):
        if D[i][j]=='W':
            q.append((i,j))
            v[i][j]=1
while q:
    x,y=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if D[nx][ny]=='.' and v[nx][ny]==0:q.append((nx,ny));v[nx][ny]=1
        else:
            while 1:
                if D[nx][ny]=='#':
                    nx-=dx[i]
                    ny-=dy[i]
                    break
                elif D[nx][ny]=='.':
                    break
                nx+=dx[i];ny+=dy[i]
            if v[nx][ny]==0:
                q.append((nx,ny))
                v[nx][ny]=1
for i in range(n):
    for j in range(m):
        if D[i][j]=='.' and v[i][j]==0:
            D[i][j]='P'
for i in range(n):
    print(''.join(map(str,D[i])))