프로그래머스 43163 단어 변환 자바 풀이

난이도 : Lv. 3

풀이일 : 2411144

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

프로그래머스

---

문제

---

아이디어

• BFS로 탐색한다.
• queue를 사용해서 현재 단어와 현재까지의 변환 횟수를 저장한다.
• words 안의 모든 단어에 대해 현재 단어와 몇 글자가 다른지 비교 작업을 한다.
• 현재 단어와 한 글자만 다른 단어로 변환하고, 변환 단어와 변환 횟수를 queue에 추가한다.
• 목표단어에 도달할 경우, 변환 횟수를 반환하고, 끝까지 도달하지 못하면 0을 출력한다.

---

풀이 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] visited = new boolean[words.length + 1];
        Queue<String> queue = new LinkedList<>();
        queue.add(begin); // 시작단어
        queue.add("0"); // 변환 횟수
        
        while (!queue.isEmpty()) {
            String now = queue.poll();
            String count = queue.poll();
            
            for (int i = 0; i < words.length; i++) {
            	// 현재 단어와 새 단어의 다른 알파벳 수 확인
                String word = words[i];
                int miss = 0;
                for (int j = 0; j < word.length(); j++) {
                    if (now.charAt(j) != word.charAt(j)) {
                        miss++;
                    }
                }
                // 한글자만 다르고, 변환에 거쳐온 적 없는 단어일 경우
                if (miss == 1 && !visited[i]) {
                    if (word.equals(target)) {
                        return count.length(); // 변환 횟수 출력
                    }
                    queue.add(word); // 바꿀 단어 추가
                    queue.add(count+"0"); // 변환 횟수 추가
                    visited[i] = true; // 방문 표시
                }
            }
        }   
        return answer;
    }
}

• visited : 각 단어의 방문 여부를 확인
• queue : (현재단어, 현재까지의 변환횟수) 를 저장
• miss : now와 word의 각 자리 알파벳 비교 후, 다르면 miss 증가
• 다른 글자가 한 개 뿐이고, 아직 방문하지 않은 단어라면 방문
• 변환할 단어가 목표 단어라면, 현재까지의 변환 횟수 + 1 반환
• 변환할 단어가 목표 단어가 아니라면, 변환한 새 단어, 변환횟수를 queue에 추가하고 방문 표시

---

느낀점

• 파이썬에서는 큐에 (단어, 변환횟수)를 넣는 방식으로 풀었는데, 자바에서는 그런건 할 줄을 몰라서 조금 이상하게 풀었다. 문자열 0을 변환 횟수만큼 추가해서, 최종적으로 0의 개수를 출력했는데 대체 이게 무슨 코드야.
• 맨날 자바에서 x, y좌표 추가할 때도 두 개씩 넣고 두 개씩 뽑고 있는데, 이렇게 미루다가는 평생 미룰 것 같으니까 어떻게 하는 건지 좀 찾아보고 정리해야지.
• 자바로도 코드 깔끔하게 잘 짜고 싶어

---

2412183 개선코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    class Node {
        String term;
        int count;
        
        public Node(String term, int count) {
            this.term = term;
            this.count = count;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] visited = new boolean[words.length + 1];
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(begin, 1));
        
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                int miss = 0;
                for (int j = 0; j < word.length(); j++) {
                    if (now.term.charAt(j) != word.charAt(j)) {
                        miss++;
                    }
                }
                if (miss == 1 && !visited[i]) {
                    if (word.equals(target)) {
                        return now.count;
                    }
                    queue.add(new Node(word, now.count + 1));
                    visited[i] = true;
                }
            }
        }   
        return answer;
    }
}

수정 사항

• queue 에 현재 단어와 변환 횟수를 함께 담을 수 있도록 Node 클래스를 추가하고, 큐를 사용했다.
• 이제 이렇게 쓰는 방법 배워서 신이 나서 수정해봤다.

---

실행 결과