2178 : 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

readline 은 뒤에 '\n' 까지 입력으로 받는다고 함! 그래서 rstrip()으로 제거

rstrip : 문자열에 오른쪽 공백이나 인자가된 문자열의 모든 조합을 제거

 

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
maze = []

for _ in range(n):
    maze.append(list(map(int, input().rstrip())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(a, b):
    queue = deque()
    queue.append((a,b))

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            next_a = a + dx[i]
            next_b = b + dy[i]

            if 0 <= next_a < n and 0 <= next_b < m and maze[next_a][next_b] == 1:
                queue.append([next_a, next_b])
                maze[next_a][next_b] = maze[a][b] + 1

    return maze[n-1][m-1]

print(bfs(0,0))

 

처음 입력

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

코드 실행 후

3	0	9	10	11	12
2	0	8	0	12	0
3	0	7	0	13	14
4	5	6	0	14	15