[Baekjoon] -2178. 미로 탐색
import sys
def bfs(r, c):
global result
Q.append([r, c])
visited[r][c] = 1
while Q:
temp = Q.pop(0)
for i in range(4):
nr = temp[0] + dx[i]
nc = temp[1] + dy[i]
if 0 <= nr < N and 0<= nc < M:
if maze[nr][nc] == '1' and visited[nr][nc] == 0:
visited[nr][nc] = visited[temp[0]][temp[1]] + 1
if nr == N-1 and nc == M-1:
result = visited[nr][nc]
return result
Q.append([nr, nc])
return result
N, M = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
Q = []
result = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
print(bfs(0, 0))
🔑 전형적인 bfs문제이다.
칸을 셀 때에는 시작 위치와 도착 위치도 포함해야하기때문에 거리값조정에 주의하자~!
문제에서는 (1, 1)에서 출발해야한다 했는데 나는 인덱스값이 0부터 시작하기에 시작위치를 (0, 0)으로 주었다.
Author And Source
이 문제에 관하여([Baekjoon] -2178. 미로 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jjiani/Baekjoon-2178.-미로-탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)