알고리즘 문제
[백준] 2178번 미로 탐색
feelcoding
2020. 1. 10. 19:29
728x90
단계별로 풀어보기 DFS와 BFS의 5단계 문제
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
BFS로 풀면 된다.
큐에 (row, col, depth)를 집어넣는다. (row, col)은 방문한 위치, depth는 (1, 1)부터 몇 칸 거쳐서 왔는지 정보이다.
from sys import stdin
import collections
n, m = list(map(int, stdin.readline().split()))
matrix = []
for i in range(n):
matrix.append(stdin.readline())
q = collections.deque()
q.append((0, 0, 1))
visited = [[False] * m for i in range(n)]
while q:
cur = q.popleft()
if not visited[cur[0]][cur[1]]:
visited[cur[0]][cur[1]] = True
if cur[0] == n - 1 and cur[1] == m - 1:
print(cur[2])
break
else:
continue
if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == "1" and not visited[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1], cur[2] + 1))
if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == "1" and not visited[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1, cur[2] + 1))
if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == "1" and not visited[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1], cur[2] + 1))
if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == "1" and not visited[cur[0]][cur[1] - 1]:
q.append((cur[0], cur[1] - 1, cur[2] + 1))
728x90