항해99 26일차 TIl( 단어 변환 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

• target -> start로 가는 길 찾기
•  DFS ? BFS?
  • 이와 같은 단어 찾기 아니면 백트래킹 DFS
  • 최소 횟수이니까 최단 거리? BFS
• 최소 횟수 = 최단 거리로 판단, BFS 구현

 

BFS를 이해하기 쉽게 디버깅 넣은 코드

import java.util.*;
  class Word {
    String name;
    int index;
    int cnt;
    
    Word(String name, int index, int cnt) {
        this.name= name;
        this.index = index;
        this.cnt = cnt;
    }
    }


class Solution {
  
    //BFS 활용
    public int solution(String begin, String target, String[] words) {
        int n = words.length;
        boolean[] visited = new boolean[n];
        Queue<Word> q = new LinkedList<>();
        
        //처음에 begin 큐에 넣어주기
        q.add(new Word(begin, -1, 0));        
        String lastName ="";
        int answer = 0;
        if(Arrays.asList(words).indexOf(target) == -1)
            return 0;
        while(!q.isEmpty()) {
            Word word = q.poll();
            System.out.println("q poll: " + word.name);
            String name = word.name;
            int index = word.index;
            int cnt = word.cnt;
           //begin을 걸러내기 위해
            if(index != -1)
                visited[index] = true;
            System.out.println("name: " + name + " index: " + index + " cnt: " + cnt);
            if(name.equals(target)) {
                return cnt;
            }
            for(int i = 0; i < words.length; i++) {
                if(!visited[i] && compare(name, words[i])) {
                    q.add(new Word(words[i], i, cnt+1));
                            System.out.println("Elements in the queue:");
                            for (Word w : q) {
                                System.out.println(w.name);
                            }
                                                System.out.println();

                }
            }
        }
       return 0;
    }
    
        //글자 비교 함수
    public boolean compare(String s1, String s2) {
        int cnt = 0;
        for(int i =0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                cnt++;
            }
        }
        if(cnt == 1)
            return true;
        else{
            return false;
        }
    }
}

 

sout 없앤 코드

import java.util.*;
  class Word {
    String name;
    int index;
    int cnt;
    
    Word(String name, int index, int cnt) {
        this.name= name;
        this.index = index;
        this.cnt = cnt;
    }
    }


class Solution {
  
    //BFS 활용
    public int solution(String begin, String target, String[] words) {
        int n = words.length;
        boolean[] visited = new boolean[n];
        Queue<Word> q = new LinkedList<>();
        
        //처음에 begin 큐에 넣어주기
        q.add(new Word(begin, -1, 0));        
        String lastName ="";
        int answer = 0;
        if(Arrays.asList(words).indexOf(target) == -1)
            return 0;
        while(!q.isEmpty()) {
            Word word = q.poll();
            String name = word.name;
            int index = word.index;
            int cnt = word.cnt;
           //begin을 걸러내기 위해
            if(index != -1)
                visited[index] = true;
            if(name.equals(target)) {
                return cnt;
            }
            for(int i = 0; i < words.length; i++) {
                if(!visited[i] && compare(name, words[i])) {
                    q.add(new Word(words[i], i, cnt+1));
                }
            }
        }
       return 0;
    }
    
        //글자 비교 함수
    public boolean compare(String s1, String s2) {
        int cnt = 0;
        for(int i =0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                cnt++;
            }
        }
        if(cnt == 1)
            return true;
        else{
            return false;
        }
    }
}

 

배움

• Arrays.asList(String 배열).indexOf 

DFS 코드 

 

• BFS 코드보다 10배는 빠르다
• 이유는?
  •  

class Solution {
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);
        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            int k = 0;    // 같은 스펠링 몇개인지 세기
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            if (k == begin.length() - 1) {  // 한글자 빼고 모두 같은 경우
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }
}