알고스팟

아직 푸는 중입니다.

생각한 방법은 뚫린 곳(0으로 표시된 곳)은 bfs로 탐색하고, 벽이 있으면(1로 표시) 오른쪽, 아래쪽 벽을 뚫어서 길로(0으로) 바꿉니다.
m,n을 bfs로 지나칠 때까지 반복합니다.

반례
6 5
001011
111100
110110
101000
000010

이 케이스에서 (지나온 길을 8로 표시, -1은 보기 불편함)

x,y : 0 1
deque([(1, 1), (0, 2)])
[8, 8, 0, 0, 1, 1]
[1, 0, 1, 1, 0, 0]
[1, 1, 0, 1, 1, 0]
[1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]

x,y : 0 2
deque([(1, 2)])
[8, 8, 8, 8, 1, 1]
[1, 0, 0, 1, 0, 0]
[1, 1, 0, 1, 1, 0]
[1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]

이렇게 되는데, 내가 생각한 대로 짜였다면

[8, 8, 8, 8, 0, 1]
[1, 0, 1, 0, 0, 0]
[1, 1, 0, 1, 1, 0]
[1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]

이 되어야 합니다.

어디가 잘못되었는지 확인하고 빠른 시일내에 업데이트하겠습니다 :)

from collections import deque

m,n = map(int, input().split())
graph = []

for i in range(n):
    graph.append(list(map(int,input())))

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

graph[0][0] = 8 # 지나온 길은 8로 표시
def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    wall = 0
    count = 1
    while graph[n-1][m-1] == 0:
        
        flag = False
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]        
                if nx >= n or ny >= m or nx < 0 or ny < 0:
                    continue
                if graph[nx][ny] != 0:
                    continue
                graph[nx][ny] = 8
                queue.append((nx,ny))
                    
        if graph[n-1][m-1] == 8:
            break
            
        for i in [1,3]:
            nx = x + dx[i]
            ny = y + dy[i]        
            if nx >= n or ny >= m or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                flag = True
                queue.append((nx,ny))
            
        if flag == True:
            wall += 1
        
        print("**********after**********")
        print("x,y :", x,y)
        print(queue)
        for i in range(n):
            print(graph[i])
        print("\n")
        
        count += 1
        if count > 10:
            break
    return wall

print(bfs(0,0))