코딩 테스트를 치면서 실무에서 자주 사용하는 해쉬, 문자열 관련 문제들은 비교적 수월하게 풀었지만, 내가 실무에서 자주 사용할 일이 없는 탐색이나 그래프 문제가 나오면 항상 고전을 하였다.
그렇기에 내가 약했던 유형을 위주로 문제를 풀어보며 정리를 해보려고 한다.
오늘 정리할 코딩 테스트 문제는 프로그래머스의 '단어 변환' 문제로 dfs를 활용해 풀 수 있는 레벨 3 문제였다.
개인적으로 재귀함수를 효과적으로 사용할 수 있다면 어렵지 않게 풀 수 있는 문제였다고 생각한다.
class Solution {
static boolean[] check;
static int answer = 0;
public int solution(String begin, String target, String[] words) {
check = new boolean[words.length];
dfs(begin, target, words, 0);
return answer;
}
public void dfs(String begin, String target, String[] words, int count){
if(begin.equals(target)){
answer=count;
return;
}
for(int i=0; i<words.length; i++){
if(check[i] == true){
continue;
}
int same = 0;
for(int j=0; j<begin.length(); j++){
if(begin.charAt(j) == words[i].charAt(j)){
same++;
}
}
if(same == begin.length()-1){
check[i] = true;
dfs(words[i], target, words, count+1);
check[i] = false;
}
}
}
}
마지막 7번 값을 설정하는 것을 깜빡하고 왜 정상적인 값이 나오지 않는지 고민을 했었다.
아직 까지도 dfs 문제가 문자열 유형의 문제처럼 자유롭게 머릿속에서 그려지지는 않지만, 해당 유형의 문제를 지속적으로 풀어봐서 자연스러워지게 만들어야 할 것 같다.