728x90
단계별로 풀어보기 DFS와 BFS 9단계 문제
이렇게 짰는데
from sys import stdin
n, m = 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, 1, False))
visited = [[False] * m for i in range(n)]
flag = False
while q:
cur = q.popleft()
if cur[0] == n - 1 and cur[1] == m - 1:
print(cur[2])
flag = True
break
if not visited[cur[0]][cur[1]]:
visited[cur[0]][cur[1]] = True
else:
continue
if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == '0' and not visited[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1], cur[2] + 1, cur[3]))
if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == '0' and not visited[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1], cur[2] + 1, cur[3]))
if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == '0' and not visited[cur[0]][cur[1] - 1]:
q.append((cur[0], cur[1] - 1, cur[2] + 1, cur[3]))
if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == '0' and not visited[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1, cur[2] + 1, cur[3]))
if not cur[3] and cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == '1':
q.append((cur[0] - 1, cur[1], cur[2] + 1, True))
if not cur[3] and cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == '1':
q.append((cur[0] + 1, cur[1], cur[2] + 1, True))
if not cur[3] and cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == '1':
q.append((cur[0], cur[1] - 1, cur[2] + 1, True))
if not cur[3] and cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == '1':
q.append((cur[0], cur[1] + 1, cur[2] + 1, True))
if not flag:
print(-1)
틀렸다고 한다.
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 10870번 피보나치 수5 (0) | 2020.01.12 |
---|---|
[백준] 10872번 팩토리얼 (0) | 2020.01.12 |
[백준] 1697 숨바꼭질 (0) | 2020.01.10 |
[백준] 7569번 토마토 (0) | 2020.01.10 |
[백준] 7576번 토마토 (0) | 2020.01.10 |