BOJ 2206 벽 부수고 이동하기

백준 2206 링크

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

풀이방법

파이썬으로 dequeue를 쓰는게 안 익숙해서 이상한데서 시간을 끌었다...

 

그냥 pop하면 안되고 popleft해야됨..

 

만약 pop을 시키지 않고 맨 앞의 요소에 그냥 접근만 하고싶으면 q[0] 으로 할 수 있어요

 

처음엔 깔끔하게 짠거같은데 오류 잡는다고 이것저것 확실히 하다보니까 더러워진 느낌

 

저는 이 문제를 풀때 dp[y][x][벽을 뚫고 지나갔는지 여부]이걸 통해서 풀었지만, 다시 한번 생각해보니 dp[y][x]로만 해도 충분하다고 생각했었습니다. 

 

왜냐하면, 벽을 뚫었는지 여부는 그냥 큐를 통해서 기록해주면 된다고 생각했기 때문입니다. 이미 뚫고 지나갔는지 확인해서 이미 뚫었다면 벽을 안지나가면 되는거고, 안뚫었다면 뚫는 것까지 생각해서 진행해 주면 되니까요.

 

그런데 다음과 같은 반례를 어떤 분에게 받았습니다. 잘하시더군요

 

7 4 
0000 
1110 
0000 
0111 
0000 
0011 
0010

이 반례는 (1,0)~(1,2)에서 최소값으로 벽뚫는데 걸려버립니다. 그래서 끝까지 가지를 못하더군요 마지막에 벽이 또있으니까.

 

결과적으론 제 생각이 틀렸다는겁니다. 😢

코드

from collections import deque
input=__import__('sys').stdin.readline
n,m = map(int, input().split())
mp = [(input()) for _ in range(n)]
d = [[[-1]*2 for _ in range(m)] for _ in range(n)]
d[0][0][0] = 1
q=deque([(0,0,0)])
dx,dy=[0,0,1,-1],[1,-1,0,0]
while q:
    y,x,z = q.popleft()
    if y==n-1 and x==m-1:
        continue
    for i in range(4):
        ny,nx = y+dy[i],x+dx[i]
        if ny>=0 and ny<=n-1 and nx>=0 and nx<=m-1:
            if z==0 and mp[ny][nx]=='1' and d[ny][nx][1]==-1:
                d[ny][nx][1]=d[y][x][0]+1
                q.append((ny,nx,1))
            if mp[ny][nx]=='0' and d[ny][nx][z]==-1:
                d[ny][nx][z]=d[y][x][z]+1   
                q.append((ny,nx,z))
if d[n-1][m-1][0]==-1 and d[n-1][m-1][1]==-1:
    print(-1)
elif d[n-1][m-1][0]!=-1 and d[n-1][m-1][1]!=-1:
    print(min(d[n-1][m-1]))
elif d[n-1][m-1][0]==-1 or d[n-1][m-1][1]==-1:
    print(max(d[n-1][m-1]))