[프로그래머스, Java] 단어 변환

사진을 클릭하면 해당 문제로 이동

⭐ 아이디어

모두를가지고~~ -> dfs (stack)
가능한 최소의 경우 -> bfs (queue)

begin hit
target cog

words 안에 target이 없으면 return 0

(begin, count=0)을 stack에 넣고 시작

while(!isEmpty)
꺼낸값과 하나만 차이나는 단어 찾기 -> 어떻게 최적화?
    target의 index로 분기하기
    현재 target(i) 와 pop(i)가 같으면 넘어가
    다르다면 -> pop(i)를 target(i)로 변경한 전체 문자를 words에서 찾기
            -> 찾았다면 해당 단어로 변경하고 count+1 하기
            -> target과 같다면 answer 와 count를 크기비교하여 작은 값을 저장하기
            -> 같지 않다면 다시 stack에 넣기

return answer;

---

❌풀이 1 (실패)

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = Integer.MAX_VALUE;
        List<String> wordList = Arrays.asList(words);


        Deque<String[]> stack = new ArrayDeque<>();
        stack.push(new String[]{begin, "0"});

        StringBuilder sb = new StringBuilder();

        while(!stack.isEmpty()) {
            String[] current = stack.pop();
            String word = current[0];
            int count = Integer.parseInt(current[1]);

            if(word.equals(target)) {
                System.out.println(word + " : " + count);
                answer = Math.min(count, answer);
                continue;
            }

            //꺼낸값과 하나만 차이나는 단어 찾기
            for(int i = 0; i < target.length(); i++) {
                // 현재 target(i) 와 pop(i)가 같으면 넘어가
                if(word.charAt(i) == target.charAt(i)) {
                    continue;
                } else {
                    sb.append(word);
                    sb.replace(i, i+1, String.valueOf(target.charAt(i)));
                    String newWord = sb.toString();
                    System.out.println("newWord : " + newWord);

                    if(wordList.contains(newWord)) {
                        count++;
                        System.out.println("newWord : " + newWord + " count : " + count);
                        stack.push(new String[]{newWord, String.valueOf(count)});
                    }
                    sb.setLength(0);
                }
            }
        }
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
}

target과 유사한 값만 찾는게아니라 다른값으로 변환될 수도 있어야함

 

예를 들어

begin이 "hit"

target가 "cog"

words가 ["hot","dot","dog","lot","log","cog"]라면

"hit" -> "hot" -> "dot" -> "dog" -> "cog" 처럼 dog 등으로 우회할 수 있어야하는데 이부분을 고려못함

 

설계 오류

 

💡풀이

- 노드를 만들어서 활용

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution2 {
    class Node {
        String name;
        int count;

        Node(String name, int count) {
            this.name = name;
            this.count = count;
        }
    }
    public int solution(String begin, String target, String[] words) {

        if(!Arrays.asList(words).contains(target)) return 0;

        int answer = 0;

        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(begin, 0));

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

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            String name = current.name;
            int count = current.count;

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

            for(int i = 0; i < words.length; i++) {
                if(visited[i]) {
                    continue;
                }
                if(isEqualWithOneDiff(name, words[i])) {
                    visited[i] = true;
                    queue.offer(new Node(words[i], count + 1));
                }
            }
        }

        return 0;
    }

    boolean isEqualWithOneDiff(String word1, String word2) {
        int count = 0;

        for(int i = 0; i < word1.length(); i++) {
            if(word1.charAt(i) != word2.charAt(i)) {
                count++;
            }
        }

        return count == 1;
    }
}

- 문제에서 한번만 방문해야 된다는 부분을 파악하지 못해서 조금 헤매기도 했다.

visited를 활용하였고 글자 비교 로직은 별도의 함수로 분리해서 가독성을 높힐 수 있었다.

---

📖새로 배운 부분

1. 최단 경로 탐색에는 DFS가 아닌 BFS를 사용해야 합니다. 너비 우선 탐색(BFS)은 시작점부터 가까운 순서로 탐색하므로, 목표 지점에 처음 도달하는 순간이 항상 최단 경로임을 보장합니다.
2. 그래프 탐색 시 방문 기록(visited)은 필수입니다. 한 번 처리한 노드를 다시 큐에 넣는 것을 방지하여 무한 루프에 빠지지 않고, 중복 계산을 피해 효율적인 탐색이 가능해집니다.
3. 복잡한 조건 판별은 별도의 함수로 분리하는 것이 좋습니다. 두 단어가 한 글자만 다른지 확인하는 로직을 별도 함수로 만들면, 메인 로직이 간결해지고 가독성이 높아져 실수를 줄일 수 있습니다.

---

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.