BFS 문제 회고 2

이번 문제는 효율성에 관한 문제이다.

지도와 관련된 BFS문제였다 여느 지도 문제와 동일하게 한번 간 곳은 못가고 도착 지점까지 가장 짧은 길을 찾는 문제였다.
가장 짧은 길을 찾아야하니 BFS인 것은 알았지만 효율성에서 계속 실패했는데 3가지 이유가 있었다.

1. len()
   참 단순한 문제이다 제일 MAX_X, MAX_Y 표현 할때 아무생각없이 전역 으로 사용할 변수를 선언한것이아니라 len(map)으로 표현해 반복을 돌며 계속해서 len을 계산했다. 다시 찾아보니 시간복잡도가 len(map)이여도 이미 python내부에서 len을 데이터 저장 시 지정하기때문에 새로이 계산하지는 않는다고 한다.

2. 지나온 길 표시
   나같은 경우에는 리스트를 통해서 이미 지나왔던 곳은 표시를 했는데 not in을 통해서 확인했고 그 과정에서 시간 복잡도를 잡아먹었다. 해결법으로 이미 지나온길은 지도에 바로 불가능 지역으로 표시하는 것이다.

3. 지나온 길 표시 시점
   처음에는 반복문에 들어서면 첫 과정으로 현재길을 불가능 지역으로 만드는 것이였다. 하지만 이럴경우 BFS의 특성으로 넓이 우선 탐색을 하다 한번 들렀던 구역을 다시 들리는 불상사가 발생할 수 있다.(가지치며 나아가다가)
   그래서 queue에 넣어줄 때 미리 map에 표시해 미리 방지했다.