리트코드 그래프 문제 추천리스트에 있었던 미로에서 가장 가까운 탈출구로 도망가야 하는 문제다. BFS유형의 문제는 내가 볼때 두가지의 패턴으로 나뉜다. 하나는 일반적인 Queue 자료구조를 이용한 가능한 모든 경우의 수 찾기, 그리고 Priority_Queue 를 이용한 가장 짧은 구간/혹은 경로 찾기. 그리고 이 둘중에 무엇을 쓸지 고민이 된다면 난 이렇게 정의 할거같다. PQ같은경우는 가중치가 존재하는 경로에서 가장 짧은 구간을 찾을때 사용하고 그 외인 경우는 그냥 Q만 사용하더라도 찾을수가 있다. 예전에 가중치가 존재하는 Matrix문제에서 일반적인 Queue 구조를 쓰려했다가 당했던 기억이 있는것처럼 잘 구분하면서 쓰면 좋을거같다.
이번 BFS문제는 생각보다 간단했다. 다만 일반적으로 0,0에서 시작하는게 아니라 entrance 라는 시작지점이 있었고 이 entrance 구간에서 한번만 움직여 탈출할수 있는 곳은 문제가 원하는 탈출구가 아니라는걸 중요시 했다. 즉, 한번 움직일때 (동,서,남,북) 최소한의 level은 0 이상이여야 한다는것이다.
처음에는 bool 값을 써가지고 표현할까도 싶었지만 굳이 그럴필요 없이 만약 level 이 0 이상이고 탈출구가 보인다면 바로 해당 레벨을 리턴하면 되는 문제였다. 그리고 그 외에 탈출구가 아닌곳들, 혹은 벽이 보인다면 continue 를 해서 무시해 주었다. BFS 든 DFS든 항상 내가 갔던 경로를 체크해주는것이 가장 중요한거같다. 그렇기 때문에 나는 먼저 q구조안에 좌표를 넣어주고 나서는 해당 좌표값들을 모두 벽으로 만들었고 내가 출발 했던 포인트도 방향 루프가 끝나면 벽으로 만들어주었다.
BFS에 대한 개념 정도만 가지고 있었다면 쉽게 풀수 있었던 문제같다.
배운점:
1. 일반적인 Queue 와 Priority_Queue 를 구분해서 사용하는 방법.
2. BFS에서 나올수있는 여러 컨디션들을 생각할것.
