9. DFS & BFS - 단어변환

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java
DFS & BFS 단어변환

BFS를 재귀로 진행

main 메서드

1. 단어들 중에 목표단어가 없는 경우 0을 return
2. 있는 경우 bfs( 0, 시작단어 ) 를 호출한후 최솟값 return

코드

for(String word:words){
    if(word.equals(target)){
        bfs(0, begin);
        return min_case + 1;
    }
}
return 0;

bfs 메서드 ( 재귀 )

changable이 true인 단어들을 교체과정에 추가하며 비교한다.

선언부

void bfs(int depth, String current)
int depth : 재귀가 실행된 횟수이자 교체 과정에 단어가 추가 된 횟수
String current : 현재 단어

구현부

boolean [] visited = new boolean [단어들의 총 갯수]

• 교체 과정에서 사용된 단어는 true 사용안된 단어는 false

재귀 탈출 조건

1. 성공한 교체과정의 횟수의 최솟값보다 depth가 클 때
   ( 이미 더 짧은 교체 과정을 구했다는 뜻이기에 바로 리턴 )
   ( 최솟값의 초기값은 총 단어의 갯수에 1을 더한 값 )
2. changable( current, 목표단어 ) 가 true 일 때
   ( depth 가 교체과정의 횟수가 최솟값보다 작을경우 최솟값에 depth 를 저장하고 탈출)

1. 모든 단어들을 차례차례 비교하며 사용되지 않은 단어고 changable이 true인 경우 해당 단어를 방문함으로 바꾸고 재귀를 호출한다.
   bfs(depth+1, 바뀔 단어)
2. 다시 방문하지 않음으로 바꾸어 준다. 이번단어를 사용하지 않은 상태로 다음 단어를 사용한 케이스를 비교하기 위해서

코드

void bfs(int depth, String current){
    //이미 적은횟수의 변환으로 target을 만든 경우
    if( depth > min_case) return;
    //target으로 변환 가능시 min_case값보다 적게 변환했을 경우 min_case에 변환횟수(depth)를 저장
    if( changable(current, target) ){
        min_case = Math.min(min_case, depth);
        return;
    }
    //변환가능한 단어를 찾으면 변환 후 다음 재귀하여 다음 변환가능 단어를 찾게
    for( int i = 0;i<words.length;i++){
        //이미 변경에 사용된 단어일 경우
        if(visited[i])continue;
        if(changable(current, words[i])){
            visited[i] = true;
            bfs(depth+1, words[i]);
            visited[i] = false;
        }
    }
}

changable 메서드

a 단어와 b 단어가 다른 글자가 1개일 때 true를 반환 아니면 false

선언부

boolean changable(String a, String b)

구현부

• 방어 코드 : 두 단어가 같으면 false를 반환

1. 두단어의 글자들은 앞부터 하나씩 비교하여 다를 경우 diff를 1개씩 증가시킨다.
   ( diff가 1이상이 되면 즉시 false 반환 )
2. 중간에 false가 반환되지 않았다면 return true

코드

boolean changable(String a, String b){
    int diff = 0;
    for(int i=0;i<a.length();i++){
        if(a.charAt(i) != b.charAt(i)){
            if( ++diff > 1 )
                return false;
        }
    }
    return true;
}

프로그래머스용 코드

class Solution {
    boolean [] visited;
    int min_case;
    String target;
    String [] words;
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        min_case = words.length;
        this.target = target;
        this.words = words;
        //words에 target이 있을시 bfs()호출 후 min_case 리턴
        for(String word:words){
            if(word.equals(target)){
                bfs(0, begin);
                //begin추가한 갯수
                return min_case + 1;
            }
        }
        //words에 target이 없으니 0 리턴
        return 0;
    }
    void bfs(int depth, String current){
        //이미 적은횟수의 변환으로 target을 만든 경우
        if( depth > min_case) return;
        //target으로 변환 가능시 min_case값보다 적게 변환했을 경우 min_case에 변환횟수(depth)를 저장
        if( changable(current, target) ){
            min_case = Math.min(min_case, depth);
            return;
        }
        //변환가능한 단어를 찾으면 변환 후 다음 재귀하여 다음 변환가능 단어를 찾게
        for( int i = 0;i<words.length;i++){
            //이미 변경에 사용된 단어일 경우
            if(visited[i])continue;
            if(changable(current, words[i])){
                visited[i] = true;
                bfs(depth+1, words[i]);
                visited[i] = false;
            }
        }
    }
    boolean changable(String a, String b){
        int diff = 0;
        for(int i=0;i<a.length();i++){
            if(a.charAt(i) != b.charAt(i)){
                if( ++diff > 1 )
                    return false;
            }
        }
        return true;
    }
}