[프로그래머스] 단어변환(Level 3)

📝문제 링크

프로그래머스 > 깊이/너비 우선 탐색 > 단어 변환 문제보기

🔑문제 KeyPoint

예제만 보고 단순하게 words[]배열을 순차적으로 접근하며 판단하는 문제라고 생각했다.
그래서 words[] 순서대로 1번에서 2번, 2번에서 3번 단어대로 변환가능하면 방문여부를 체크하여 쉽게 풀었다. 결론은 이렇게 풀면 당연히 안된다🙅‍♂️🙅‍♀️🙅‍♂️

그럼, 이 문제를 그림으로 그려서 이해해보자

hot으로 간 경우 dot, lot 두 가지 갈래로 접근이 가능하고 ,
이후 계속 한 글자만 다르면서 방문하지 않은 탐색하면 된다.
여기서 하나 방문여부를 체크해주는 것이 중요하다.

방문했다고 해서 방문상태를 계속 true상태로 두면 탐색에 대한 문제가 생긴다!
그러므로, 한번 방문은 해서 계속 DFS탐색을 진행한다면 그 이후에 방문여부를 false로 다시 처리해주어야 한다. ( 이 부분은 프로그래머스 - 여행경로와 유사하다. )

그래서 이 문제는 아래의 2가지만 생각해서 재귀호출로 쉽게 풀 수 있다.

1. 한 글자만 다르면서 방문하지 않은 단어를 탐색한다.
2. 종료조건은 begin == target이 같아지는 시기이다.
   (단, 단어변환이 불가능한 경우도 있기 때문에 초기 answer값을 words[]의 길이로 설정해두기로 한다.)

💻문제 풀이

단어변환을 못하는 경우를 생각하여,
dfs(String[] words, String begin, String target, int count) count 변수로 체크를 하려고 했는데, 이미 방문을 다 한 상태라면 더 이상 재귀호출을 하지 않아 신경쓰지 않아도 된다.

int answer = 0;
boolean[] visited;		// 방문 여부 체크

public int solution(String begin, String target, String[] words) {
    visited = new boolean[words.length];
    answer = words.length;
    dfs(words, begin, target, 0);
    return answer == words.length ? 0 : answer;
}

public void dfs(String[] words, String begin, String target, int count) {
    // 종료시점은 begin , target이 같은 경우 ( 단어변환이 불가능한 경우, 재귀호출이 종료된다)
    if(begin.equals(target)) {
        answer = Math.min(answer, count);
        return;
    }

    for(int i=0;i<words.length;i++) {
        if(wordCheck(begin, words[i]) && !visited[i]) {
            visited[i] = true;
            dfs(words, words[i], target, count+1); 
            // 현재 단어로 dfs를 탐색했다면, 방문여부를  false로 처리해준다. 
            visited[i]=false;
        }
    }
}

// 한 글자만 다른지 체크
public boolean wordCheck(String a, String b) {
    int cnt = 0;
    for(int i=0;i<a.length();i++) {
        if(a.charAt(i) != b.charAt(i)) cnt++;
    }
    return cnt==1 ? true : false;
}

전체 소스 보기(git)