[프로그래머스] 단어 변환 - 자바

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

프로그래머스

 

문제 풀이

1. bfs, dfs를 구현할 줄 아는가

2. 각 단계별로 몇 번 진행됐는지 카운팅 할 수 있는가

3. 단어가 변환될 수 있는지 체크할 수 있는

위 3조건만 가능하다면 나름 쉽게 구현이 가능하다

 

탐색 연습겸 bfs, dfs 둘 다 구현해보았다.

 

코드 - BFS

import java.util.*;
class Solution {
    static boolean[] vs;

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        answer = bfs(begin, target, words);
        return answer==-1? 0 : answer;
    }
    
    static int bfs(String begin, String target, String[] words){
        int len = words.length;
        vs= new boolean[len];
        
        Queue<String> q = new LinkedList<>();
        q.offer(begin);
        
        int cnt=0;
        while(!q.isEmpty()){
            for(int j=0;j<q.size();j++){
                String now = q.poll();
                
                if(now.equals(target))
                    return cnt;
                
                for(int i=0;i<len;i++){
                    if(vs[i]||!canChange(now, words[i])) continue;
                    
                    vs[i]=true;
                    q.offer(words[i]);
                }
            }
            cnt++;
        }
        return -1;
        
    }
    
    static boolean canChange(String s1, String s2){
        int cnt=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)==s2.charAt(i))
                cnt++;
        }
        return cnt==s1.length()-1?true:false;
    }
}

 

코드 - DFS

import java.util.*;
class Solution {
    static boolean[] vs;
    static String[] words;
    static int answer;
    
    public int solution(String begin, String target, String[] words) {
        this.words=words;
        vs = new boolean[words.length];
        
        dfs(begin, target, 0);
        return answer;
    }

    static void dfs(String now, String target, int cnt){
        if(now.equals(target)){
            answer=cnt;
            return;
        }

        for(int i=0; i<words.length; i++){
            if(vs[i]||!canChange(now, words[i])) continue;

            vs[i]=true;
            dfs(words[i], target, cnt+1);
            vs[i]=false;
        }
    }

    static boolean canChange(String s1, String s2){
        int cnt=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)==s2.charAt(i))
                cnt++;
        }
        return cnt==s1.length()-1?true:false;
    }

}