모각코PS / 프로그래머스 Lv3 단어 변환 & Leetcode 127 Word Ladder

모각코 PS스터디

그래프 탐색 세 번째 문제인 '단어 변환'입니다. 이 문제는 Leetcode 127번 Word Ladder 문제와 완전히 동일해요.

단어들이 배열로 주어지는데 곧바로 그래프가 떠오른다면...? 어느 정도 그래프 탐색 카테고리의 문제에 익숙해졌다고 봐도 되는 거겠죠?😇
그것만 빨리 캐치한다면 특별히 어려운 점은 없습니다.
아, BFS 탐색의 레벨을 세는 꿀팁이 있으니까, 그 부분이 필요하시다면 참고하세요! 그럼 문제 풀이로 들어가보죠!

문제와 풀이

---

문제 링크 : 프로그래머스 Lv3 - 단어 변환
문제 링크 : LeetCode Hard - Word Ladder

👇펼쳐서 코드와 해설 읽기

왜 단어를 보고 그래프를 연상할 수 있을까요?
문제의 제약조건은 사실상 이런 말로 해석이 됩니다.

"각 단어는 정점입니다. 두 개의 단어가 한 글자만 차이가 난다면, 그 사이에 무향 간선이 놓입니다."

이게 첫번째 핵심 아이디어구요(그 사이를 인접행렬로 정의해줘도 좋고, 저는 인접리스트를 만들어서 해결했습니다).
두 번째는 BFS의 탐색 레벨을 세는 것입니다. queue에서 poll()할 때마다 카운트하려 한다면 당연히 각 레벨 별로 셀 수가 없겠죠?
해결 방법은 간단하게는 두 가지 정도 있을 거 같아요.

1. 제가 이전 문제(이전 문제 풀이는 여기를 참고)에서 사용했던 접근 방식처럼, 정점 정보를 객체로 관리하며, 방문할 때에 레벨을 함께 저장하는 것.
2. while을 이중으로 구현하기.

이전 문제를 풀면서 노드를 객체로 따로 구현했었기 때문에, 다른 접근이 없나 생각해보았는데요. 분명 있을 것 같은데, 모르겠더라구요! 그래서 구글링 해보고, 내용을 정리해보았더니 2번 방법이 나왔습니다!

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

public class Nick {

    public int solution(String begin, String target, String[] words) {
        // target이 words에 존재하지 않음 -> return 0;
        boolean targetNotFound = isTargetNotFound(target, words);
        if (targetNotFound) return 0;

        // 새로운 단어 배열을 만들어줍니다. begin 단어를 배열 끝에 추가한 단어 배열이에요.
        String[] wrds = Arrays.copyOf(words, words.length + 1);
        wrds[wrds.length - 1] = begin;

        // 인접리스트 객체. 각 단어별로 연결할 수 있도록, 링크드리스트로 초기화해둡니다.
        List<String>[] adjacent = new List[wrds.length];
        for (int i = 0; i < adjacent.length; i++) {
            adjacent[i] = new LinkedList<>();
        }

        // 2. 인접리스트 생성 : 한 글자 다른 단어 간에 무향간선을 둔다.
        makeAdjacencyList(begin, wrds, adjacent);

        // 3. queue를 이용한 bfs 구현 - wrds 마지막 요소(begin)를 시작정점으로
        boolean[] visited = new boolean[wrds.length];
        Queue<String> q = new LinkedList<>();
        q.add(wrds[wrds.length - 1]);
        visited[wrds.length - 1] = true;
        int level = 0; // bfs 탐색의 레벨을 기록할 변수. return 될 값.

        while (!q.isEmpty()) {
            int size = q.size(); //한 레벨의 사이즈 만큼만 돌기 위해, 사이즈를 따로. 안쪽 반복문에서 갱신하면 절대로 안되겠죠?

            while (size-- != 0) {
                String nowString = q.poll();
                if (nowString.equals(target)) break; // 목표 정점(단어)에 도달했으면 탐색 종료.

                int nowIdx = getWordIdx(wrds, nowString); // 단어배열에서 몇번째인지 찾기(= 몇번째 링크드리스트인지 찾기)

                for (int i = 0; i < adjacent[nowIdx].size(); i++) {
                    String vertex = adjacent[nowIdx].get(i);
                    int nextWordIdx = getWordIdx(wrds, vertex);
                    if (!visited[nextWordIdx]) { // 방문처리
                        q.add(vertex);
                        visited[nextWordIdx] = true;
                    }
                }
            }
            level++;
        }

        level--; //맨 처음 단어(begin)로 인한 스텝은 빼주기.

        return level;
    }

    private boolean isTargetNotFound(String target, String[] words) { 
        boolean targetNotFound = true;
        for (String w : words) {
            if (w.equals(target)) targetNotFound = false;
        }
        return targetNotFound;
    }

    private int getWordIdx(String[] wrds, String findWord) {
        int idx = -1;
        for (int i = 0; i < wrds.length; i++) { //idx를 찾는 무식한 방법.. 개선이 필요...하지만 귀찮다.
            if (wrds[i].equals(findWord)) {
                idx = i;
                break;
            }
        }
        return idx;
    }

    private void makeAdjacencyList(String begin, String[] wrds, List<String>[] adjacent) {
        int charLength = begin.length();
        // 'i번째 단어'와 'j번째 단어'의 'k번째 글자'를 반복해나가면서 간선 여부를 파악한다
        for (int i = 0; i < wrds.length - 1; i++) { //마지막 단어는 비교할 다음 단어가 없다.
            for (int j = i + 1; j < wrds.length; j++) {
                int diff = 0;
                for (int k = 0; k < charLength; k++) {
                    if (wrds[i].charAt(k) != wrds[j].charAt(k)) diff++;
                    if (2 <= diff) break;
                }
                if (diff == 1) { // 현 단어와 다음 단어 간의 차이가 한 글자인 경우 => ?.... 생각해보면 0글자 차이인 경우는 없잖아... 하지만 코드를 수정할 여백이 부족하므로 적지 않는다.
                    adjacent[i].add(wrds[j]);
                    adjacent[j].add(wrds[i]);
                }
            }
        }
    }

}

마무리

---

사실 이번 문제는 BFS 레벨을 카운트 하는 것보다는 제안한 1번 해결책처럼, 정점을 객체로 관리하는게 훨씬 간단하고 코드도 간결했겠다는 생각이 들었어요(괜히 다른 방식으로 풀어보고 싶어가지고...). 하지만 뭐, 새로운 템플릿을 하나 배웠으니 남는 장사였던 것 같습니다!

그리고 이번 문제도 또! 이전 문제와 같이 두 분(o_b:us님, 소토님)의 코드를 참고하며 셀프 리뷰했습니다. ㅋㅋ.

저는 당연히 BFS만 떠올렸는데 두 분 다 DFS로 푸셨더라구요! DFS로 푸는 것이 더 적절한 경우인가?하는 의문이 들었습니다. 월요일 리뷰시간에 한 번 여쭤보려고요...

아 그리고 기억해둘만한, BFS 레벨 카운트(정확히는 한 레벨씩 탐색하기)하는 코드의 템플릿을 적어두며 리뷰 마치겠습니다. 감사합니다!

// 기억해둘 만한 코드템플릿 : bfs 레벨 카운트 - 한 레벨의 탐색을 마칠 때마다 step count
int step = 0; //bfs 탐색 step을 저장할 변수
while (!queue.isEmpty()) {
    int size = queue.size(); // 한 레벨의 사이즈를 저장해두고

    while (size-- > 0) { // 해당 횟수만큼만 큐 요소를 확인
        // do something
    }

    step++; // 한 레벨의 요소를 다 확인했으면 step을 카운트.
}