이 게시글에는 프로그래머스의 "코딩테스트 연습" 메뉴중에서 DFS/BFS 파트에 있는 "단위 변환" 문제에 대한 풀이 및 소스 코드가 나와있습니다. 만약 풀이를 보고싶지 않다면 뒤로가기를 눌러주세요.
나는 보통 DFS, BFS로 둘 다 풀 수 있는 문제는 DFS로 푸는 편이다. 만약 시간 초과가 나거나 BFS로도 풀어보고 싶을 때는 BFS로 풀지만 웬만하면 DFS로 해결하는 편이다.
그래서 이번 문제도 처음은 DFS로 접근했다. 재귀함수를 만들어서 해결했다.
소스코드
function solution(begin, target, words) {
let answer = Number.MAX_VALUE;
testWord(begin, [], 0); // 재귀함수 호출
// answer가 변하지 않으면 변환 불가
if (answer === Number.MAX_VALUE) return 0;
// 그렇지 않으면 최소 변환 수 반환
else return answer;
// 실제 재귀함수 구현 부분
function testWord(newWord, visitedIndex, cnt) {
if (newWord === target) {
if (answer > cnt) answer = cnt;
return;
}
// newWord가 words 중 하나로 변환될 수 있는지 검사하는 파트
for (let i = 0; i < words.length; i++) {
// 이전에 변환되었던 것들은 제외한다
if (visitedIndex.includes(i)) continue;
const nextWord = canChange(newWord, words[i]);
// 변환 가능한 단어가 있으면 그 단어로 다시 재귀함수 호출
// 호출하면서 방문배열 및 cnt를 적절히 변경해준다
if (nextWord) {
testWord(nextWord, [...visitedIndex, i], cnt + 1);
}
}
}
// 바꿀 수 있는 단어가 있으면 그 단어를 반환하고,
// 아닌 경우에는 빈 문자열을 반환한다.
function canChange(from, to) {
let cnt = 0;
for (let i = 0; i < from.length; i++) {
if (from[i] !== to[i]) {
cnt++;
}
if (cnt >= 2) return '';
}
return to;
}
}answer는 최소 변환 횟수와 비교를 해야하기 때문에 최댓값으로 설정해주었다. 만약 0으로 설정한다면 항상 0이 최소값이 될 것이기 때문이다.
대부분의 설명은 주석에 달아놓긴 했지만, 정리할 겸 다시 설명해보려고 한다.
function testWord
이 함수는 "begin이 target으로 변환이 되는지 test한다"라는 의미로 testWord라고 명명해보았다. 더욱 적절한 이름이 있을 것 같은데 역시 명명하는 것이 제일 어려운 것 같다.
이 함수의 매개변수는 아래와 같은 것들이 있다.
newWord - 새로 테스트할 단어를 뜻한다.
visitedIndex - 이미 테스트했던 단어들의 인덱스를 보관한다
cnt - 몇 번 변환되었는지 세어준다
이 함수의 맨 처음에는 탈출 조건을 정해주었다. 재귀함수는 탈출조건이 없으면 스택 오버플로우가 발생하기 때문에 매우 중요하다. 여기서는 newWord가 target과 같아지면 더 이상 테스트할 필요가 없기때문에 같아지면 지금까지 세었던 cnt값을 answer와 비교한 후 return하였다.
그 다음 문제에서 주어지는 words배열을 순회하면서 newWord에서 바꿀 수 있는 단어가 있는지 확인한다. 만약 바꿀 수 있으면 nextWord를 이용해 다시 testWord를 호출한다. 이 때, cnt를 1 증가시켜 한 번 변환이 되었다는 것을 알리고, 기존에 변경하면서 지나온 단어들은 visitedIndex에 저장해 무한루프에 빠지지 않도록 처리한다.
function canChange
이 함수는의 매개변수는 아래와 같은 것들이 있다.
from - 변환되기 전 단어이다
to - 변환해서 되고 싶은 단어이다
from이 to로 하나의 알파벳만 변경해서 변환이 가능한 지 알려주는 함수이다. 원래는 testWord함수에서 같이 처리했지만, 요즘 리팩터링을 공부하면서 따로 함수로 뺄 수 있는 부분은 빼 보았다. 확실히 로직이 눈에 더욱 잘 들어오는 것 같다.
소감
처음에는 무작정 코드부터 작성해서 실패했었다. 그 후, 연습장에 생각을 정리하면서 어떻게 코드를 구성하고 또 재귀함수의 매개변수는 어떻게 할 지를 생각하고 나서 풀었는데 거의 바로 풀린 것 같다. 문제를 풀기 전에 꼭 생각을 정리해서 노트나 주석으로 남긴 후에 문제를 푸는 습관을 들여야 할 것 같다. 무작정 문제부터 풀기 시작하면 스스로 정리도 안되어서 막히면 문제를 푸는 데에 더욱 긴 시간이 들어가기 때문이다.
그리고 testWord의 함수의 반환 값을 answer에 넣어주는 편이 더 깔끔한 코드일 것 같다는 생각이 든다. 물론 그렇게 한다면 answer대신 최솟값을 비교하는 변수를 두어야 한다.
주말에 시간을 내어서 BFS로도 풀어보면 좋을 것 같다. 또, 지금까지 풀었던 문제중에 정리하고 싶은 문제들이 있는데 이는 따로 시간을 내어서 한 번 블로그에 남겨봐야겠다.
