최근에 봤던 코딩 테스트에서 봤던 문제랑 가장 유사하다고 생각해서 생각난김에 다시 풀어보았다. 최근에 백준에서 연습을 할때도 대부분 시뮬레이션을 조합한 BFS 방식을 많이 쓰다보니깐 나도 모르게 그게 되게 편해지고 익숙해져서 그래프 문제를 봤을때 BFS 옵션부터 생각하고 풀게되서 진짜 힘들게 문제를 풀었던거같다. 상황에 따라서, 또 문제에 따라서 DFS 와 BFS가 번갈아가면서 쓰여지는데 좀 생각못하고 했던거같다.
DFS 가 이 문제에서 쓰여야 하는 이유로는 모든 경우의 수를 봐야하고 이동하는 경로가 word 랑 매칭이 되야하기 때문이다. 최소 경로 등등이 아니라 하나의 시작점에서 만들 수 있는 모든 경우의 수를 확인해야 함으로 BFS를 썼다면 굉장히 어지러운 상황이 됐을거고 겹치는 경로를 못가기 때문에 절대로 답을 못구했을거다.
원래 나는 DFS류의 문제를 풀떄 visited 같은 space 를 또 사용하지 않고 matrix 안에서만 해결을 하는데 그냥 이렇게 쓰는게 더 마음 편한거같다. 하나의 경로로 갔을떄 매칭이 안된다면 돌아오고 그 과정에서 이미 방문했던 경로는 바꿔놓으면 된다. 저번에 풀었던 문제처럼 상황에 따라서 방문하는 경로가 달라질수 있는 조건이 붙는다면은 모든 경로를 탐색할수 있는 DFS를 답으로 쓰면은 훨씬 좋을거같다.
배운점:
- BFS와 DFS의 활용
- 문제 잘 읽기
성장하는 사람