LV3 단어 변환 (Java)

 

---

 

문제

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

프로그래머스

풀이

단순한 dfs 문제이다. 방문 여부를 따지면서 모든 경우의 수를 체크해보면 된다.

 

단 문자열에서 문자 하나만 다를경우 해당 문자열로 바꿀 수 있기에 그 부분만 잘 체크하면 무난하게 풀 수 있다.

 

코드

import java.util.*;

class Solution {
    
    public boolean[] visited;
    public int answer = Integer.MAX_VALUE;

    public boolean diff(String a, String b){
        int cnt = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) cnt+=1;
        }
        return cnt == 1 ? true : false;
    }
    
    public void recursive(int cnt, String now, String target, String[] words){
        if(cnt >= words.length) return;
        
        if(now.equals(target)){
            answer = Math.min(cnt,answer);
            return;
        }
        
        for(int i=0; i<words.length; i++){
            // 방문하지 않은 문자열이면서, 문자열 차이가 1개라면.
            if(visited[i] == false && diff(now, words[i])){
                visited[i] = true;
                recursive(cnt+1, words[i], target, words);
                visited[i] = false;
            }
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        recursive(0, begin, target, words);
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
}

 

후기

아직도 charAt 이 친구가 어색하다...