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

🦊 내 풀이

import java.util.*;

class Solution {
    
    //두개의 알파벳이 겹치는지 확인
    public boolean isDuplicate(String originWord, String compareWord){
        int count = 0;
        
        for(int i=0; i<originWord.length(); i++){
            if(originWord.charAt(i) == compareWord.charAt(i)){
                count++;
            }
        }
        return count == compareWord.length()-1;
    }
    
    public int findTarget(String target, String[] words){
        for(int i=0;i<words.length;i++){
            if(words[i].equals(target)){
                return i;
            }
        }
        return -1;
    }
    
    public int solution(String begin, String target, String[] words) {
        int[] visited = new int[words.length];
        Queue<Integer> q = new LinkedList<>();
        
        // target 이 없는 경우 바로 0 리턴
        if(!Arrays.toString(words).contains(target)){
            return 0;
        }
        
        // 초기 세팅
        for(int i=0;i<words.length;i++){
            if(isDuplicate(begin, words[i])){
                q.add(i);
                visited[i] = 1;
            }
        }
        
        while(!q.isEmpty()){
            int index = q.poll();
            
            for(int i=0;i<words.length;i++){
                if(visited[i] == 0 && isDuplicate(words[index], words[i])){
                    visited[i] = visited[index]+1;
                    q.add(i);
                }
            }
        }
        return visited[findTarget(target, words)];
    }
}

 

처음에는 어떻게 풀어야 할지 헤맸는데, 한번에 하나의 알파벳만 바꿀 수 있다는 것에 힌트를 얻어 출발했다.

또한 dfs 는 경로의 값을 저장해야 하는 경우에 사용한다는 것도 기억하고 있었기에 이를 활용했다.

 

1. 목적지가 될 수 있는 단어를 찾고 (isDuplicate 메서드의 역할) 

2. 아직 방문하지 않았고 + 겹치는 단어라면 큐에 넣고 해당 dp 의 값을 이전 경로의 값에서 1 더한 값으로 업데이트 해준다. 

 

🦊 다른 사람의 풀이

class Solution {

    static class Node {
        String next;
        int edge;

        public Node(String next, int edge) {
            this.next = next;
            this.edge = edge;
        }
    }

    public int solution(String begin, String target, String[] words) {
        int n = words.length, ans = 0;

        // for (int i=0; i<n; i++)
        //  if (words[i] != target && i == n-1) return 0;

        Queue<Node> q = new LinkedList<>();


        boolean[] visit = new boolean[n];
        q.add(new Node(begin, 0));

        while(!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.next.equals(target)) {
                ans = cur.edge;
                break;
            }

            for (int i=0; i<n; i++) {
                if (!visit[i] && isNext(cur.next, words[i])) {
                    visit[i] = true;
                    q.add(new Node(words[i], cur.edge + 1));
                }
            }
        }

        return ans;
    }

    static boolean isNext(String cur, String n) {
        int cnt = 0;
        for (int i=0; i<n.length(); i++) {
            if (cur.charAt(i) != n.charAt(i)) {
                if (++ cnt > 1) return false;
            }
        }

        return true;
    }    
}

내가 좋다고 생각한 풀이는 위와 같다.

나의 경우에는 target 이 등장해도 멈추지 않고 queue 가 비어있지 않은 동안에는 계속해서 while 문이 돈다.

그러나 위의 코드같은 경우에는 target 이 등장하면 while 문이 멈추고 ans 값이 업데이트 된다.

또한, 나의 경우에는 visited 라는 배열에 일일이 경로의 값을 저장해 주었는데 위의 코드에는 간단하게 visited 여부만 저장해두고 간선의 값은 필요한 간선만 (target까지 가는 경로의 값만) 저장하고 업데이트하기에 더 효율적이라고 생각했다.