BOJ 2206벽 부수고 이동하기 Python

문제

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

접근 1

최단거리를 찾아야 하니 bfs를 이용할 건데 목표 지점까지 갈 때 벽을 한번 부수고 이동할 수도 있다
그래서 큐에 넣는 과정에서 자신의 좌표와 해당 좌표에 도달할 때까지 벽을 부쉈는지를 기억하게 하고 코드를 짜보았다

코드1

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())
board = list([list(map(int,input().rstrip())) for _ in range(n)])
board[0][0] = 1
veclst = [(1,0),(-1,0),(0,-1),(0,1)]

def bfs():
    q = deque([[0,0,0]])
    while q:
        now = q.popleft()
        if now[0] == n-1 and now[1] == m-1:
            return board[now[0]][now[1]]
        for vec in veclst:
            vy,vx,b = now[0]+vec[0],now[1]+vec[1],now[2]
            if 0<= vy <n and 0<= vx < m:
                if board[vy][vx] == 0:
                    q.append([vy,vx,b])
                    board[vy][vx] = board[now[0]][now[1]]+1
                elif board[vy][vx] == 1 and b == 0:
                    q.append([vy,vx,b+1])
                    board[vy][vx] = board[now[0]][now[1]]+1
    return -1
print(bfs())

결과 1

답은 틀린 거로 나왔다 문제에서 알려준 예제 입력은 통과되었는데 틀렸다고 나와서 이것저것 생각해 보니
벽을 부수고 갈 수 있는 경로 A와 벽을 부수지 않고 돌아서 갈 수 있는 B가 있을 때
벽을 부수고 간 A의 경로가 더 짧을 경우 벽을 부수지 않고 돌아온 경로 B가 경로 A 좌표에 도착했을 때
이미 방문한 것으로 처리되어 B의 경로로는 도착지점까지 탐색이 불가능하다 예시로
입력
4 6
010000
010110
010111
000110
이 주워졌을 때 벽을 부수고 마지막 지점에 도달할 수 있지만 위의 코드로는 출력이 -1이 나온다.
탐색 조건을 수정해서 제출해 보려 했지만 어떻게 할지 잘 떠오르지 않아 다른 사람의 코드를 참조해서 해결했다

코드2

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())
board = list([list(map(int,input().rstrip())) for _ in range(n)])
vislist = [[[0]*2 for _ in range(m)] for _ in range(n)]
vislist[0][0][0] = 1

veclst = [(1,0),(-1,0),(0,-1),(0,1)]

def bfs():
    q = deque([[0,0,0]])
    while q:
        now = q.popleft()
        if now[0] == n-1 and now[1] == m-1:
            return vislist[now[0]][now[1]][now[2]]
        for vec in veclst:
            vy,vx,b = now[0]+vec[0],now[1]+vec[1],now[2]
            if 0<= vy <n and 0<= vx < m:
                if board[vy][vx] == 1 and now[2] == 0:
                    vislist[vy][vx][1] = vislist[now[0]][now[1]][0]+1
                    q.append([vy,vx,1])
                elif board[vy][vx] == 0 and vislist[vy][vx][now[2]] == 0:
                    vislist[vy][vx][now[2]] = vislist[now[0]][now[1]][now[2]] +1
                    q.append([vy,vx,now[2]])
    return -1
print(bfs())

결과 2

입력받은 행렬을 3차원 리스트로 따로 만들어 탐색하는 방식이다
이번 문제는 좀 더 시간을 썼으면 해결했을 거 같은데 아쉽다