BFS 와 시뮬레이션 타입의 문제를 풀어보았다. 솔직히 체감상? 골드5 의 문제라고는 했는데 다 풀고나니 어렵게 느껴졌다. 문제가 요구하는 조건을 잘 인지 못하고 풀었으면 무조건 에러가 났을거같고 애초에 정답비율도 23프로에 머무르고 있는거보면 어려운 문제이긴 하다.
일반적인 탐색 문제라고 생각할수 있지만 조건이 추가되었다. 0,0 좌표에서 시작하는 캐릭터가 가장 끝에 있는 칸까지 가기 위해서 상하좌우로 움직일수 있는데 Time 이라는 변수가 주어지고 시간이 다 되면 Fail 을 한다. 그리고 특이한거는 맵에 보면 칼이 하나 떨어져있는데 이 칼을 줍게되면은 벽으로 이루어진 공간조차도 다 뚫을수 있다 한다. 그리고 마지막 칸 까지 갔을때 나올수있는 최단거리를 리턴하면 된다.
나는 처음에 이 코드를 적을때 PQ를 활용하는 방법을 했고 distance 를 토대로 상하좌우 탐색을 하며 테스트 케이스를 잘 통과했다. 그러나 답을 제출하자 메모리 오류가 심각하게 났었고 내 BFS 탐색에 틀린점을 바로잡았다.
우선, BFS류의 탐색에는 Q의 넣는순간 Visited 벡터에서 체크를 해주는게 맞는거같다. 리트코드에서 풀었던 문제 중에 굳이 그렇게 안해도 코드가 돌아가는거때매 오해를 많이 했는데 만약 같은 조건에서 테스트케이스가 통과한다면 메모리 오류를 막기위해 그렇게 하는 조건이 좋은거같다.
추가적으로 이 문제에서는 일반적인 visited 표시가 아니고, 칼을 얻었을때와 없을때 이동하는 경로 또한 다르고, 칼이 없이 지나갔던 경로도 칼을 들고 지나가게 되면, 아무리 같은 경로여도 벽을 뚫을수있기 때문에 더 빠른 path 가 된다. 그렇기때문에 이 문제의 핵심은 visited 벡터를 짜주는 거였던거같다.
배운점:
1. Q에 넣은후에는 꼭..체크해주자 visited
2. 변형된 visited 벡터
