문제

해법을 생각해보자.

방법 1: 그냥 떠오르는 대로

  • bfs로 0,0부터 탐색
  • 가장 먼저 N,M 도착하면 출력하기
  • n^2
  • 구현
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    from collections import deque

directions = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0],
]

VISITED = -1
TARGET = '1'

queue = deque()
queue.append([0,0,1])
maze_list[0][0] = VISITED

while(len(queue) > 0):
    x, y, count = queue.popleft()

    if x == n - 1 and y == m - 1:
        print(count)
        break

    for i in range(4):
        nx = x + directions[i][0]
        ny = y + directions[i][1]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if maze_list[nx][ny] != TARGET:
            continue
        maze_list[nx][ny] = VISITED
        queue.append([nx, ny, count + 1])