오랜만에 올려보는 코딩테스트 문제이다. 지금까지 굉장히 많은 DFS/BFS 류의 문제를 풀어봤지만 이 문제는 솔직히 조금 고민 많이 했었고 내가 지금까지 풀었던 방식에 조금 변화를 주자라고 결심을 하기도 했다.
Matrix 위에는 동전 두개가 놓여있다. 그리고 이동 방향은 상,하,좌,우 이지만 한번 움직일때 두개에 동전이 "동시에" 움직인다. 그리고 코드가 끝나는 조건은 둘 중 "하나"에 코인이 밖으로 떨어질때 10이 넘지 않는 최소값 거리를 리턴하면 되는 문제이다.
이 문제를 처음 읽었을때 생각했던 점 중 하나는, 동전은 두개가 동시에 움직이기에 만약 둘 중 하나의 동전이라도 벽에 닿는 상황이 나온다면 움직이지 못한다고 생각했던 것이었다. 그러나 내가 문제를 잘 못이해했던 점은, 둘 중 하나의 동전이 벽에 닿는다 해도 벽에 닿지 않는 나머지 하나의 동전은 계속 이동이 가능하단 점이었다. 여기서 부터 내 코드의 변경점이 좀 필요했고 다른 필요 조건들도 고려했었다.
이 문제를 처음 풀었을때 바보같이 했던 점은 동전이 두개가 들어간다는 점에서 내 PQ를 두번 팝 해줬단것이었다. 이 문제를 시작할때 중요하게 설계해야 되는 부분은 동전1 과 동전2의 좌표를 동시에 저장했어야 했던것이다. 내가 선택한 탐색 방법은 BFS였고 이 동전 두개의 distance 를 따로 저장할 필요가 없었던것이다.
맨 처음 좌표 저장(1)
//BFS (2)
여기서 내가 기존에 풀던 방식을 변경 해야겠다 생각했던거는 난 원래 Visited 를 안쓰고 기존에 Matrix를 직접 변경하여서 Visited 스페이스를 줄였다. 그런데 직접 Check 벡터를 사용하다보니 좀 더 직관적으로 코드를 이해하기 편했다. 앞으로는 BFS 탐색에서는 Visited를 적극적으로 사용해보고 싶다. 코드는 되게 직관적이긴하다. 리턴 조건은 무조건 one_fall() 하나가 떨어졌을때 리턴해주었고 만약에 dist가 10이 넘어간다면 -1을 리턴해주었다.
그 외에는 check_wall 이란 함수를 사용해주면서 둘중 하나라도 벽에 닿지 않는경우에는 이동 좌표, 닿는경우에는 원래 좌표를 넣어주었다.
마지막으로는 두 동전 전부 이동 가능할때는 visited를 이용하여 이미 방문한곳이 아니기에 둘 다 이동해주었다.
check_wall 과 both_fall 같은경우 이해를 바로 할수있지만 one_fall() 같은 경우는 XOR 이라는 표시를 처음 해주었따. XOR 은 둘중 하나만 true 일 경우 1을 리턴해준다.
배운점:
1. XOR 의 활용
2. BFS에서 Visited 를 이용한 탐색
3. 문제 조건 잘 읽기
