프로그래머스 - 미로 탈출 (L2)

 1from collections import deque
 2
 3vx = [0, 0, -1, 1]
 4vy = [-1, 1, 0, 0]
 5
 6def bfs(maps, N, M, p1, p2):
 7    visited = [[False]*M for _ in range(N)]
 8    q = deque()
 9    q.append(list(p1)+[0])
10
11    while q:
12        curY, curX, cnt = q.popleft()
13
14        if p2 == (curY, curX):
15            return cnt
16
17        for i in range(4):
18            x = curX + vx[i]
19            y = curY + vy[i]
20            if 0 <= x < M and 0 <= y < N and not visited[y][x] and maps[y][x] != 'X':
21                visited[y][x] = True
22                q.append([y, x, cnt+1])
23    return -1
24
25def solution(maps):
26    answer = 0
27    N = len(maps)
28    M = len(maps[0])
29
30    sp = (0, 0)
31    lp = (0, 0)
32    ep = (0, 0)
33
34    for i in range(N):
35        for j in range(M):
36            if maps[i][j] == 'S':
37                sp = (i, j)
38            elif maps[i][j] == 'L':
39                lp = (i, j)
40            elif maps[i][j] == 'E':
41                ep = (i, j)
42
43    tmp = bfs(maps, N, M, sp, lp)
44    if tmp == -1:
45        return -1
46
47    answer += tmp
48
49    tmp = bfs(maps, N, M, lp, ep)
50    if tmp == -1:
51        return -1
52
53    answer += tmp
54
55    return answer