프로그래머스] 단어 변환

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

프로그래머스

 

풀이

바꿀수있는단어를 큐에담아 bfs진행

 

import java.util.*;

class Solution {
    static boolean[] visited;
    static int n;
    static int result =0;
    
    public int solution(String begin, String target, String[] words) {
        /*
        문자의 차이가 1개인 단어를 찾아서 bfs진행
        */
        
        n = words.length;
        visited = new boolean[n];
        
        bfs(target,words,begin);
      
        return result;
        

    }
    
    static void bfs(String target, String[] words, String current)
    {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(current,0));    
        
        while(!q.isEmpty())
        {
            Node currentNode = q.poll();
            String c = currentNode.word;
            int currentStep = currentNode.step;
            
            if(c.equals(target))
            {
                result = currentStep;
                return;
            }
            
            for(int i=0;i<n;i++)
            {
                if(!visited[i])
                {
                    String compareString = words[i];

                    if(checkString(c,compareString))
                    {
                        // System.out.println(compareString);
                        visited[i] = true;
                        q.add(new Node(compareString,currentStep+1));
                    }
                }
            }
            
            
        }
    }
    
    static boolean checkString(String current, String compare)
    {
        int length = current.length();
        int count =0;
        
        char[] c1 = current.toCharArray();
        char[] c2 = compare.toCharArray();
        
        for(int i=0;i<length;i++)
        {
            if(c1[i] == c2[i])
            {
                count ++;
            }

        }
        
        if(count == length -1)
        {
            return true;
        }

        return false;
        
    }
    
    static class Node{
        String word;
        int step;
        
        public Node(String word,int step)
        {
            this.word = word;
            this.step = step;
        }
    }
    
    
    
}

 

 

2. dfs사용

뽑을수있는 모든 경우를 보려면 visited를 true했던걸 false로 바꾼다.

가장 적은 횟수로 정답에 도달한것을 구한다.

import java.util.*;

class Solution {
    static boolean[] visited;
    static int n;
    static int result =Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        /*
        문자의 차이가 1개인 단어를 찾아서 bfs진행
        */
        
        n = words.length;
        visited = new boolean[n];
        
        dfs(target,words,begin,0);
        
        if(result == Integer.MAX_VALUE)
        {
            return 0;
        }
        return result;
        

    }
    
    static void dfs(String target, String[] words, String current, int step)
    {

        if(current.equals(target))
        {
            result= Math.min(result,step);
            return;
        }
        
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                String compareString = words[i];

                if(checkString(current,compareString))
                {
                    System.out.println(compareString);
                    visited[i] = true;
                    dfs(target,words,compareString,step+1);
                    visited[i] = false;
                }
            }
        }
        
        
    }
    
    
    static boolean checkString(String current, String compare)
    {
        int length = current.length();
        int count =0;
        
        char[] c1 = current.toCharArray();
        char[] c2 = compare.toCharArray();
        
        for(int i=0;i<length;i++)
        {
            if(c1[i] == c2[i])
            {
                count ++;
            }

        }
        
        if(count == length -1)
        {
            return true;
        }

        return false;
        
    }
    
    static class Node{
        String word;
        int step;
        
        public Node(String word,int step)
        {
            this.word = word;
            this.step = step;
        }
    }
    
    
    
}