99클럽 코테 스터디 14일차 TIL - 43163 단어 변환

43163. 단어 변환 / c++ / level3 / 18분

문제 및 코드

접근 방식

그래프 탐색 / DFS

1. 두 단어가 하나의 문자만 다른 경우 해당 단어로 바꿀 수 있다면, 두 단어를 이어진 두 노드라고 볼 수 있다.
2. 단어를 순회하면서 해당 단어와 한 문자만 다른 단어를 찾아 unordered_map<string, vector> adjMap 에 넣는다.
3. 이 때 주의할 점은, 시작 단어는 words에 포함되어 있지 않기 때문에, wordgs 순회 전 begin도 words에 넣어줘야 한다.
4. 그리고 DFS에 사용하기 위한 방문 기록용 unordered_map<string, boo> vistedMap을 선언하고, words를 순회할 때 모든 단어를 false로 초기화 해준다.
5. adjMap 초기화가 끝나면 begin을 시작점으로 해서 DFS를 진행
6. DFS의 매개변수인 vector& path 의 마지막 단어가 target일 경우 path.size() 가 answer 보다 작다면 answer 를 초기화 해준다. (이 때 사용한 answer는 미리 MAX값으로 초기화)
7. DFS가 끝나고 answer 가 여전히 MAX이면 0을 반환, 아니라면 answer를 반환한다. (나는 DFS를 위해 path에 시작값으로 begin을 넣어놨었기 때문에, answer-1을 반환했다.)

생각해 볼 점

1. DFS를 사용하면 백트래킹을 활용하여 경로탐색이 용이하다는 점을 다시금 느낄 수 있었다.
2. begin을 미리 words에 넣어서 순회를 돌리는 것이 좋았다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL