프로그래머스 문제풀이(알고리즘) - 단어 변환

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

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

 

시도 1

단어 사이에 변환 될 수 있는 경로가 있다고 생각을 했고

따라서 너비 우선 탐색을 통해서 문제를 풀기로 함

처음엔 늘 그렇듯 절차지향적인 코드로 시작

public int solution(String begin, String target, String[] words) {

    List<String> wordList = new ArrayList(Arrays.asList(words));

    if (!wordList.contains(target))
        return 0;

    String[] newWords = new String[words.length + 1];
    newWords[0] = begin;
    int end = 0;
    for (int i=0; i<words.length; i++) {
        newWords[i + 1] = words[i];
        if (words[i].equals(target)) {
            end = i + 1;
        }
    }


    // 시작 단어와 간선이 있는지 확인
    List<LinkedList<Integer>> graph = new ArrayList<>();
    for (int i=0; i<newWords.length; i++) {
        graph.add(new LinkedList());
    }

    // 단어와 차이가 오직 1개이면 간선이 있음
    for (int i=0; i<newWords.length; i++)
        for (int j=0; j<newWords.length; j++) {
             if (isThereAnyRoad(newWords[i], newWords[j]))
                graph.get(i).add(j);
        }


    boolean[] isDiscover = new boolean[newWords.length];
    isDiscover[0] = true;
    Queue<Integer> searchList = new LinkedList<>();
    searchList.add(0);

    int[] depth = new int[newWords.length];
    int[] parent = new int[newWords.length];

    while (!searchList.isEmpty()) {

        int searched = searchList.poll();

        LinkedList<Integer> g = graph.get(searched);


        for (int i=0; i<g.size(); i++) {
            int discovered = g.get(i);

            if (!isDiscover[discovered]) {
                isDiscover[discovered] = true;
                searchList.add(discovered);
                parent[discovered] = searched;
                depth[discovered] = depth[searched] + 1;
            }
        }

    }

    return depth[end];
}


public boolean isThereAnyRoad(String begin, String target) {
    int deff = 0;

    for (int i=0; i<begin.length(); i++) {
        if (begin.charAt(i) != target.charAt(i))
            deff++;
    }

    return deff == 1;
}

 

시도 2

문제를 풀고 나니 다른 사람의 풀이를 볼 수 있었고 조금 더 절자지향적으로 코드를 리펙토링함

public int solution(String begin, String target, String[] words) {

    int result = 0;

    boolean[] visit = new boolean[words.length];

    Queue<Node> searchList = new LinkedList<>();
    searchList.add(new Node(begin, 0));

    while (!searchList.isEmpty()) {

        Node searched = searchList.poll();

        if (searched.getStr().equals(target)) {
            result = searched.getDepth();
            break;
        }

        for (int i=0; i<words.length; i++)
            if (!visit[i] && searched.isThereEdge(words[i])) {
                visit[i] = true;
                searchList.add(new Node(words[i], searched.getDepth() + 1));
            }

    }

    return result;
}

static class Node {
    private String str;
    private int depth;

    public Node(String str, int depth) {
        this.str = str;
        this.depth = depth;
    }

    public String getStr() {
        return str;
    }

    public int getDepth() {
        return depth;
    }

    public boolean isThereEdge(String target) {
        int deff = 0;

        for (int i=0; i<str.length(); i++) {
            if (str.charAt(i) != target.charAt(i))
                deff++;
        }

        return deff == 1;
    }
}