다시 기초를 다지자는 마인드로 원래는 자신이 있어서 안해도 된다는 마인드를 가졌던 그래프 탐색 문제에 좀 더 도전을 하게 되었다. 제목은 다르지만 내용만 보면은 이 문제는 예전에 리트코드에서 풀었떤 Find number of Enclaves 같은 문제와 비슷하다는 생각을 하게 되었다. 사실 이 문제는 물어보는것을 이해하는게 가장 큰 관건이었던거 같다.
나는 문제를 처음 풀었을때 BFS류의 문제라는것을 알았지만 바로 맞추지는 못했다, 왜냐면은 안전지대와 가장 가까운 상어와의 거리를 구하고 가장 넓은 안전거리를 출력해야 하는 문제인데 나는 아기상어의 거리와 다른 상어와의 거리를 구할려고 했었기에 쌩뚱맞은 결과가 나왔던것이다. 즉, 이 문제는 탐색을 아기상어부터 시작하는게 아니라 안전지대 에서부터 진행했어야지 답을 얻을 수 있었던거다.
기본 세팅이다. 기존에 내 블로그를 읽던 사람이라면 알았지만 난 원래 Matrix를 먼저 설정하지 않지만 이 문제는 그렇게 했다. 그리고 원래는 vector 구조를 만들어서 Q를 만들려고 했겠지만 이번에는 Struct 를 활용해봤다 (예전에 이거때문에 고생했던 적이 있었다)
visited 구조는 새로운 안전지대에서 계산을 할때마다 바뀌어야 했기에 memset 을 해주었고 이거때문에 내가 벡터를 안사용했던거도 있었다. 안전지대에서부터 BFS를 진행했다.
내가 BFS를 쓰던 구조가 조금 바뀐거같은데 나는 사실 PQ구조로 최소 거리를 구하고는 했었다. 그러나 방향을 바꿔서 일단 BFS로도 이런 식의 구조가 된다는것을 알았다. 내 생각에는..? Matrix든 Graph든 움직이는 방향에서 어떤 Weight 가 있지않는 이상 PQ의 활용의 중요성은 잘 모르겠다. 최소 거리 또한 BFS로 도 구할수 있었고 기본에 충실하며 움직인 장소는 모두 Visited 에 표시해주었다.
이렇게 코드를 쓰면은 쉽게 답이 나온다.
배운점:
1. 기본기에 충실한 탐색
2. 문제를 잘 읽자
