프로그래머스 알고리즘 - 단어변환

프로그래머스 알고리즘 - 단어변환

☞ 단어변환 문제 링크

문제의 핵심은 각 word를 노드로 두고,  변환 가능한 word간에는 간선(edge)로 연결해둔 다음에 그래프 탐색을 진행하면 어렵지 않은 문제 였습니다.

☞ 그래프(Graph) DFS 탐색 구현하기

문제풀이

• 코드의 전체적인 틀은 그래프 탐색을 응용합니다.

class Graph {
    private Word[] words;
    . . .
}

• 입력값의 문자를 이용한 만든 클래스 Word를 그래프 탐색의 노드(Node)로 치환합니다.

class Word {
    private String name;
    private List<Word> changeable; //인접 노드(Word)들을 저장하는 리스트
    private boolean visited;
    . . . 
}

• 주어진 word와 기준 word가 '한글자만' 틀린 문자의 경우는, 기준 word의 변환할 수 있는 목록(List)으로 저장해둡니다.

class Word {
    . . .
    boolean checkChangeable(Word word) {
        int countIncorrect = 0;
        for (int i = 0; i < name.length(); i++) {
            if (this.name.charAt(i) != word.getName().charAt(i)) {
                countIncorrect++;
            }
            if (countIncorrect > 1) {
                return false;
            }
        }
        return countIncorrect == 1;
    }

    void addChangeable(Word[] words) {
        for (Word word : words) {
            if (checkChangeable(word)) {
                changeable.add(word);
            }
        }
    }
}

• word 중에 target과 일치하는 것이 없다면 결과값은 0입니다.

class Graph {
    . . .
    boolean checkTargetExist() {
        for (Word word : words) {
            if (word.getName().equals(target)) {
                return true;
            }
        }
        result = 0;
        return false;
    }
}

• 모든 경로를 그래프 탐색 하면서 target과 일치하는 word가 나온다면, 현재까지 건너온 단계 수(step)를 현재 저장되어 있는 result와 비교하고 작은 수를 result에 저장합니다.

class Graph {
    . . .
    void findShortestPath(Word word, int step) {
        if (word.isVisited()) {
            return;
        }
        if (word.getName().equals(target)) {
            if (result == -1) {
                result = step;
            }
            result = Math.min(step, result);
            return;
        }
        . . .
    }
}

• 노드를 방문 했을 때, 해당 노드를 방문했다는 표식을 남기고, 해당 노드를 빠져나갈 때 노드를 방문하지 않았다는 표식을 남깁니다. (이렇게 해야 모든 경로를 탐색 할 수 있습니다.)

class Graph {
    . . .
    void findShortestPath(Word word, int step) {
    . . .
        word.setVisited(true);
        for (Word w : word.getChangeable()) {
            findShortestPath(w, step + 1);
        }
       word.setVisited(false);
}

배운점

1. 그래프 탐색 구현을 까먹지 않고 해냈다!
2. 경로 탐색 문제들에서 항상 막혔던 부분이 이미 방문했던 노드들의 방문 표식을 언제 false로 바꿔 줄까 였는데, for문이 돌고 나서 dfs메소드를 빠져나가지 전에 하면 됐다! 비슷한 문제들도 이런식으로 접근 해야겠다.
3. 문제 카테고리가 DFS/BFS인지 몰랐다면 문제의 풀이를 생각해내기 어려웠을 것 같다. 언제 그래프 문제를 쓰는지 조금은 감이 잡힌 것 같다. 요소가 있고 그 요소를 순차적으로 이동한다거나, 몇단계를 이동했는지 묻는 문제가 있다면 그래프 탐색을 떠올려야 겠다.

---

☞ 풀이 Git hub 주소