깊이/너비 우선탐색(DFS / BFS) : 단어변환 ( 프로그래머스 / java )

programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

 

* 해결과정

프로그래머스 레벨별 풀이는 모두 유형을 제공하고 있습니다. 이미 힌트를 얻는다는 점에서 해결책을 떠올리는 과정은 성장할 수 없으나 연습하기는 좋습니다. 이 문제는 DFS, BFS 모두로 해결이 가능한 문제입니다. 그 중에 저는 DFS로 풀었습니다.

 

DFS로 풀 때 항상 주의해야 할 것이 있습니다.

종료조건, 반복내용 + 백트래킹, 답을 찾는 매개변수 선정

 

종료조건을 제대로 설정하지 않으면 무한정 재귀를 반복하여 오류가 날 것이고, 반복적으로 확인하는 내용이 최신의 상황을 반복하지 못하면 마찬가지로 계속 같은 검사만 합니다. 또한 매개변수로 전해들어가는 DFS 특성상, 우리가 구해야 하는 최소값, 최대값, 총 합 등은 변수로 선언하는 것보다 매개변수에 전달하는 것이 좋습니다.

 

그렇다면, 우리는 1개를 제외한 나머지 알파벳의 같은 위치, 같은 단어를 확인하면 됩니다!

 

DFS의 조건들을 살펴보았습니다.

 

반복 내용 + 백트래킹 : 만약 알파벳 길이가 3이면 같은 위치, 같은 알파벳을 검사해 2개가 되는 단어들을 찾습니다. 새롭게 발견한 것은 visited = true로 바꾼 후 다시 재귀로 들어갑니다. + visited=false를 통한 백트래킹. 그렇다면 재귀로 들어가서 visited를 통해 true인 단어들은 지나치고 새로운 단어만 검색이 가능합니다.

 

종료 조건 : 우리가 찾은 단어와 target이 같으면 그 순간 answer와 비교하여 최신화합니다. 

 

답을 찾는 매개변수 선정 : 단어를 찾을 때마다 sum 변수에 1을 더하면서 DFS를 들어갑니다.

 

import java.util.*;
class Solution {
    
    int answer=Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {

        boolean isFind = false;
        for(int i=0;i<words.length;i++){
            if(target.equals(words[i])){
                isFind=true;
                break;
            }
        }
        if(isFind==false) return 0;
        
        boolean[] visited = new boolean[words.length];
        DFS(begin,target,words,visited,0);
        return answer;
    }
    
    public void DFS(String begin , String target, String[] words, boolean[] visited, int sum){
        for(int i=0;i<words.length;i++){
            if(visited[i] == true) continue;
            int cnt=0;
            for(int j=0;j<begin.length();j++){
                if(begin.charAt(j)==words[i].charAt(j)) cnt++;
            }
            
            if(cnt==begin.length()-1){
                if(target.equals(words[i])){
                    if(sum+1<answer){
                        answer=sum+1;
                    }
                    return;
                }
                visited[i]=true;
                DFS(words[i],target,words,visited, sum+1);
                visited[i]=false;
            }
        }    
    }
}