프로그래머스 3단계 : 단어 변환 (Java 자바)

문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

입출력 예

 

 

풀이

주어진 단어 리스트 내에서 시작 단어(begin)를 변환하여 목표 단어(target)로 바꾸는 최소 변환 과정을 구하는 문제입니다. 저는 DFS(깊이우선탐색)를 사용했습니다. DFS를 사용하여 모든 가능한 단어 변환 경로를 탐색하되, 변환이 가능한 경우에만 탐색을 진행하고, 불가능한 경우와 이미 사용한 단어는 건너뛰어 모든 가능한 경로를 탐색하며 최소 변환 과정 수를 찾아냈습니다.

 

import java.util.*;

class Solution {
    
    static int answer, n;           // 정답 및 단어 개수를 저장할 변수
    static boolean[] visit;         // 단어 방문 여부를 저장할 배열
    static List<String> list;       // 단어 리스트
    
    public int solution(String begin, String target, String[] words) {
    
        list = Arrays.asList(words); // 단어 배열을 리스트로 변환
        answer = Integer.MAX_VALUE;  // 정답을 최대값으로 초기화
        n = list.size();             // 단어 개수 저장
        visit = new boolean[n];      // 방문 배열 초기화
        
        if(!list.contains(target)) { // 변환할 수 없는 경우
            return 0;
        }
        
        dfs(begin, target, 0);       // DFS 탐색 시작
        
        return answer;               // 최소 변환 과정 수 반환
    }
    
    static void dfs(String curr, String target, int k) {
    
        if(curr.equals(target)) {    // 현재 단어가 목표 단어와 같으면
            answer = Math.min(answer, k); // 최소 변환 과정 업데이트
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(visit[i]) continue;   // 이미 사용한 단어는 제외
            if(!isAvailable(curr, list.get(i))) continue; // 변환 불가능한 경우도 제외
            
            visit[i] = true;         // 단어를 사용했다고 표시
            dfs(list.get(i), target, k + 1); // 다음 단어로 DFS 탐색
            visit[i] = false;        // 단어 사용 표시를 되돌림 (백트래킹)
        }
    }
    
    // 두 단어가 변환 가능한지 확인
    static boolean isAvailable(String s1, String s2) {
    
        int cnt = 0;
        
        for(int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            
            if(c1 != c2) cnt++;     // 다른 문자 개수 카운트
        }
        
        return cnt == 1;            // 다른 문자가 하나인 경우 변환 가능
    }
}