문제 설명
https://leetcode.com/problems/shortest-path-in-binary-matrix
BFS는 이론적으로 가장 가까운 노드부터 순차적으로 탐색하기 때문에 간선(Edge)에 가중치(weight)가 없는 그래프에 한해 Shotest path를 찾을 수 있다. 필자는 일단 기본적인 BFS 탐색 알고리즘을 알고 있었지만 해당 알고리즘만으로 경로를 찾을수는 없었다. 이를 알아내기 위해서 부모노드의 정보도 같이 visited에 저장하고 최종적으로 나온 visited의 노드의 부모를 따라 올라가면서 path를 알아낼 수 있었다.
풀이
참고로 아래 코드는 정답 Pass 를 목적으로만 작성되어 깔끔하지는 않은 코드다. 그래도 시간복잡도 면에서는 꽤 높은 등수를 기록했다.
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
queue = []
visited = []
# 맨첨에는 부모 노드가 없으니 None, None
queue.append((None,None,0,0))
# 만약 시작 노드가 1이면 그냥 -1 리턴
if grid[0][0] == 1:
return -1
# 맨 마지막 노드까지 도달 했는지를 체크하는 Flag
success = False
while queue:
parent_x, parent_y, x, y = queue.pop(0)
visited.append((parent_x, parent_y, x, y))
# 마지막에 도달하면 성공과 함께 루프 종료
if x == len(grid)-1 and y == len(grid[x])-1:
success = True
break
# x-1, y
# x-1, y+1
# x-1, y-1
# x+1, y
# x+1, y+1
# x+1. y-1
# x, y+1
# x, y-1
# 8 way로 0인 애들 queue에 넣음
# 동시에 1로 설정하여 다시는 방문 못하도록 설정
if x-1 >= 0 and grid[x-1][y] == 0:
queue.append((x, y, x-1, y))
grid[x-1][y] = 1
if x-1 >= 0 and y+1 < len(grid[x]) and grid[x-1][y+1] == 0:
queue.append((x, y, x-1, y+1))
grid[x-1][y+1] = 1
if x-1 >= 0 and y-1 >= 0 and grid[x-1][y-1] == 0:
queue.append((x, y, x-1, y-1))
grid[x-1][y-1] = 1
if x+1 < len(grid) and grid[x+1][y] == 0:
queue.append((x, y, x+1, y))
grid[x+1][y] = 1
if x+1 < len(grid) and y+1 < len(grid[x]) and grid[x+1][y+1] == 0:
queue.append((x, y, x+1, y+1))
grid[x+1][y+1] = 1
if x+1 < len(grid) and y-1 >= 0 and grid[x+1][y-1] == 0:
queue.append((x, y, x+1, y-1))
grid[x+1][y-1] = 1
if y+1 < len(grid[x]) and grid[x][y+1] == 0:
queue.append((x, y, x, y+1))
grid[x][y+1] =1
if y-1 >= 0 and grid[x][y-1] == 0:
queue.append((x, y, x, y-1))
grid[x][y-1] = 1
# 성공 못했으면 -1
if not success:
return -1
# 이제 visited를 탐색하여 실제 path를 추출한다.
# 로직은 아래와 같다.
# visited에 저장된 맨 마지막 노드의 부모 노드를 탐색
# 해당 부모노드의 부모를 탐색
# 루트 즉 부모모드가 None, None 으로 된 것까지 가면서 leng를 증가
p_x = visited[-1][0]
p_y = visited[-1][1]
#print(p_x)
leng = 0
index = -1
for index in range(len(visited)-2, -1, -1):
# 부모노드에 도달하면 종료
if p_x == None and p_y == None:
break
x = visited[index][2]
y = visited[index][3]
if p_x == x and p_y == y:
p_x = visited[index][0]
p_y = visited[index][1]
leng += 1
return leng+1