BOJ 2206(벽 부수고 이동하기)풀이

solved.ac 티어 : 골드 4

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

bfs으로 (1,1)부터 탐색을 해주는데 기회가 남아있을 때 벽을 만났다면 기회를 없애고 벽 위치를 스택에 추가해주면서 탐색을 하다가 (n, m)에 도착했을 때의 횟수를 출력하면 된다.

import sys
from collections import deque
input=sys.stdin.readline
a,b=map(int,input().split())
l=[list(input().strip())for i in range(a)]
q=deque([[0,0,1,1]])
dy=[-1,0,1,0]
dx=[0,1,0,-1]
ch=[[[0,0] for i in range(b)]for g in range(a)]
ch[0][0][1]=1
if a==1 and b==1:
    if l[0][0]=='0':
        print(1)
    else:
        print(-1)
    sys.exit()
while q!=deque([]):
    #print(q)
    y=q.popleft()
    for i in range(4):
        nx=y[1]+dx[i]
        ny=y[0]+dy[i]
        if nx==b-1 and ny==a-1:print(y[3]+1);sys.exit()
        if nx<0 or nx>=b or ny<0 or ny>=a:continue
        if ch[ny][nx][y[2]]==0:
            if l[ny][nx]=="1":
                if y[2]==1:
                    ch[ny][nx][0]=1
                    q.append([ny,nx,0,y[3]+1])
            else:
                ch[ny][nx][y[2]]=1
                q.append([ny,nx,y[2],y[3]+1])
print(-1)

 

시험 때문에 1달간 글을 안 올렸었고 이제 다시 올릴 예정이다