[백준] 1261번 (시간 초과)

1261번: 알고스팟

예상대로 시간초과가 나왔다. (1, 1)부터 (N, M)으로 가는 모든 경우의 수를 다 구해서 그 경우 벽을 몇 번 부수는지 count라는 리스트에 담아놓은 뒤에 최솟값을 출력하도록 했다. 

예상대로 시간초과가 나왔다.

from sys import stdin
m, n = list(map(int, stdin.readline().split()))
li = []
for i in range(n):
    li.append(stdin.readline())
import collections
q = collections.deque()
q.append((0, 0, 0))
visited = [[False] * m for i in range(n)]
count = []
while q:
    cur = q.popleft()
    if cur[0] == n - 1 and cur[1] == m - 1:
        count.append(cur[2])
        if cur[2] == 0:
            break
        continue
    visited[cur[0]][cur[1]] = True
    if cur[1] + 1 < m and not visited[cur[0]][cur[1] + 1]:
        if li[cur[0]][cur[1] + 1] == '1':
            q.append((cur[0], cur[1] + 1, cur[2] + 1))
        else:
            q.append((cur[0], cur[1] + 1, cur[2]))
    if cur[1] - 1 >= 0 and not visited[cur[0]][cur[1] - 1]:
        if li[cur[0]][cur[1] - 1] == '1':
            q.append((cur[0], cur[1] - 1, cur[2] + 1))
        else:
            q.append((cur[0], cur[1] - 1, cur[2]))
    if cur[0] + 1 < n and not visited[cur[0] + 1][cur[1]]:
        if li[cur[0] + 1][cur[1]] == '1':
            q.append((cur[0] + 1, cur[1], cur[2] + 1))
        else:
            q.append((cur[0] + 1, cur[1], cur[2]))
    if cur[0] - 1 >= 0 and not visited[cur[0] - 1][cur[1]]:
        if li[cur[0] - 1][cur[1]] == '1':
            q.append((cur[0] - 1, cur[1], cur[2] + 1))
        else:
            q.append((cur[0] - 1, cur[1], cur[2]))
print(min(count))