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

문제

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

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

풀이

DFS 알고리즘을 이용해서 풀었다. 

중복 체크는 HashSet<String>을 사용하였다.

dfs 함수 호출 후, 다시 visitied에 해당 값을 제거해줘야 한다.

 

소스코드

import java.util.*;
import java.lang.*;

class Solution {
    public int answer;
    public boolean flag;
    public String begin;
    public String target;
    public String[] words; 
    public HashSet<String> visited;
   
    public int solution(String begin, String target, String[] words) {
        this.answer = Integer.MAX_VALUE;
        this.visited = new HashSet<String>();
        this.begin = begin;
        this.target = target;
        this.words = words;
        
        visited.add(begin);
        dfs(begin, 0);
        
        return flag ? answer: 0;
    }
    
    public void dfs(String bf, int cnt){
        if(target.equals(bf)){
            answer = Math.min(cnt, answer);
            flag = true;
            return;
        }
        for(String af : words){
            if(canConvert(bf, af) && !visited.contains(af)){
                visited.add(af);
                dfs(af, cnt+1);
                visited.remove(af);
            }
        } 
    }
    
    public boolean canConvert(String bf, String af){
        int count = 0;
        for(int i = 0; i < bf.length(); i++){
            if(bf.charAt(i) == af.charAt(i)) count++;
        }
        return count == bf.length()-1 ? true: false; 
    }
}