오늘은 BFS 관련된 문제를 풀어보기로 했다. 이 문제는 프로그래머스에 나와있는 문제와 굉장히 유사했으며 실제로 Word Ladder 이라는 리트코드 하드문제와 동일한 문제다.
사실 하드 레벨의 난이도라고 하기 조금 민망할정도로 어려운 문제는 아니다. start 와 end, 그리고 bank 라는 벡터가 주어졌을때 end 까지 도달할수 있는 가장 짧은 경로를 리턴하면 된다. 그리고 bank 안에 있는 단어들과 하나의 글자까지 다른 단어들만 다음 후보로 허용이 되고 계속 탐색을 해서 경로 숫자를 리턴해주면 된다.
먼저 findDiff 라는 함수를 만들어서 단어와 단어 사이에 글자 차이를 계산하고 true or false 를 리턴했다.
가장 짧은 경로를 구하는 것이기 때문에 일반적인 queue 를 사용하는것보다는 priority_queue 를 사용했으며, distance 를 계속 업데이트 해주었다. 이상한 실수를 findDiff 함수에서 해가지고 찾는데 시간이 걸린게 자존심이 좀 상한다. 그리고 중복되는 단어들을 거르기 위해서 HashMap 을 이용해서 단어들을 좀 걸러주었다. 사실 이부분은 굳이 Map 아니여도 그냥 인덱스 벡터로만 했어도 충분했을거같다.
예전에 풀었던 풀이를 봐보니깐 너무 조잡했고, 일반적인 queue 를 사용한 모습이 보였었다. 그래도 코드를 짜는데 좀 더 간결해진 내 모습이 보이고 성장하고 있단거를 이럴때 느끼는거같다.
배운점:
1. Queue 와 Priority_queue 의 쓰임새
2. 코드의 간결함.
