[백준 16441번] 아기돼지와 늑대(파이썬)

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

16441번: 아기돼지와 늑대

2022.04.07 - [알고리즘 공부] - [백준 13460번] 구슬탈출 2(파이썬)

[백준 13460번] 구슬탈출 2(파이썬)

이 문제는 위의 구슬탈출 문제의 형제문제입니다.

다른 점이라면

구슬탈출은 끝까지 벽을 만날때까지 이동했지만

이건 초원or빙산이 있습니다.

 

이 문제에서 점검할 반례입니다.

 

input:
10 7
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#.#+#.#
#######

output:
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#P#+#P#
#######

 

 

오답

#######
#PP+PP#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#P#+#P#
#######

 

처음 제출하고 틀렸다고 떴길래

왜 오답일까 보다가 위의 반례를 보고 알았습니다.

 

빙산 이동해서 주의할 점은

1. 다음 이동이 벽이거나, 현재 이동한 지점이 초원이면 스탑

2. 현재 이동한 지점의 방문여부를 체크한다

 

이 두 부분입니다.

#백준 16441번 아기돼지와 늑대
from collections import deque
N,M=map(int,input().split())
room=[]
wolf=[]

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

for i in range(N):
    tmp=input().rstrip()
    tmp=list(tmp)
    for j in range(M):
        if tmp[j]=='W':
            wolf.append([i,j])
    room.append(tmp)

visited=[[False]*M for _ in range(N)]
q=deque()
for px,py in wolf:
    q.append([px,py])
    visited[px][py]=True

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

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

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]=='#':
            continue
        #빙산을 만날때
        if room[nx][ny]=='+':

            while True:
                if room[nx+dx[d]][ny+dy[d]]=='#':
                    break
                nx+=dx[d]
                ny+=dy[d]
                if room[nx][ny]=='.' or room[nx][ny]=='W':
                    break


            if visited[nx][ny]==False:
                q.append([nx,ny])
                visited[nx][ny]=True

        #그 이외에
        else:
            if visited[nx][ny]==False:
                visited[nx][ny]=True
                q.append([nx,ny])


for i in range(N):
    for j in range(M):
        if room[i][j]=='.' and visited[i][j]==False:
            room[i][j]='P'

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

 

빙산이동 구현에서 잠시 실수가 있었던 문제.

문제가 틀렸다면 조건에서 내가 빠뜨린 게 없나

다시 살펴봐야 겠네요.