알고리즘 문제
[백준] 1261번 (시간 초과)
feelcoding
2020. 1. 21. 17:11
728x90
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.
www.acmicpc.net
예상대로 시간초과가 나왔다. (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))728x90