[프로그래머스][Level3][JAVA][단어변환]

[문제 설명]

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

코딩테스트 연습 - 단어 변환

 

[문제 풀이]

문제에 나온 예시로 설명한다.

예시 > String begin = "hit";
           String target = "cog";
           String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};

 

1) String을 담는 Queue를 생성, 단어의 확인여부를 체크하는 boolean[] confirmed 를 생성한다.

2) words 배열에서 hit(begin) 과 한글자만 다른 문자열만 뽑아 Queue에 add한다. 
    그리고 해당 문자열의 index값에 대응하게 confirmed[i] = true 처리해준다.

-> confirmed[i] = true 값을 주는 이유 : 재귀를 돌면서 한글자만 다른 문자열을 추출하는데, 한 번 확인한 문자열을 또 queue에 담는 경우 무한 재귀에 빠지게 된다. 

3) begin과 한글자만 다른 문자열들을 뽑았으므로 count를 1증가시킨다. Queue에 구분자 "/"를 add한다. 

4) Queue가 isEmpty일때까지 while문을 순회한다. 

  4-1)  Queue 값을 poll하여 String s에 담는다. 

  4-2) s가 target과 같은 문자라면 count를 return하고 종료한다. 

  4-3) s가 구분자 "/" 라면 count를 1증가 시키고, 또 구분자 "/"를 넣는다. 

  4-4) s가 4-2, 4-3에도 해당하지 않는 일반 문자라면 2번과 유사하게 word배열에서 s와 한글자만 다른 문자열들을 추출하여 Queue에              add한다.
          Queue에 add한 문자열의 index에 대응하여 confirmed[i] = true값을 넣어준다. 

5) count를 return한다. 

 

느낀점 : 남들은 다 dfs로 푼것 같은데 나는 bfs로 풀어서 슬프다. 왜 나만 특이한 생각을 갖고 있는 것인가.. dfs로 푸는 방법을 얼른 알아보자.

 

[JAVA code]

- 내가 푼 bfs를 이용한 code 

package com.algorithm.programmers.level2;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test40 {
    public static void main(String[] args) {
        String begin = "hit";
        String target = "cog";
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};

        System.out.println(solution(begin, target, words));
    }

    /**
     *
     * @param begin
     * @param target
     * @param words
     * @return
     */
    public static int solution(String begin, String target, String[] words) {
        List<String> wordList = Arrays.asList(words);
        if (!wordList.contains(target)) {
            return 0;
        }

        int answer = getMinStepCount(begin, target, wordList);
        return answer;
    }

    /**
     *
     * @param being
     * @param target
     * @param wordList
     * @return
     */
    public static int getMinStepCount(String being, String target, List<String> wordList) {
        int count = 0;
        String SEPERATOR = "/";
        Queue<String> q = new LinkedList<>();
        boolean[] confirmed = new boolean[wordList.size()];

        for (int i = 0; i < wordList.size(); i++) {
            String s = wordList.get(i);
            if (isDiffOnlyOneChar(being, s)) {
                q.add(s);
                confirmed[i] = true;
            }
        }
        count++;
        q.add(SEPERATOR);

        while (!q.isEmpty()) {
            String s = q.poll();

            if (s.equals(target)) {
                return count;
            }

            if (s.equals(SEPERATOR)) {
                count++;
                q.add(SEPERATOR);
            } else {
                for (int i = 0; i < wordList.size(); i++) {
                    String w = wordList.get(i);
                    if (!confirmed[i] && isDiffOnlyOneChar(s, w)) {
                        confirmed[i] = true;
                        q.add(w);
                    }
                }
            }
        }
        return count;
    }

    /**
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean isDiffOnlyOneChar(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {

            if (count == 0 && s1.charAt(i) != s2.charAt(i)) {
                count++;
                continue;
            }

            if (count > 0 && s1.charAt(i) != s2.charAt(i)) {
                return false;
            }
        }

        return count == 1 ? true : false;
    }
}