99클럽 코테 스터디 33일차 TIL / 단어 변환(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 구현

   - DFS

공부한 내용 본인의 언어로 정리하기

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

문자열들이 주어졌을 때 처음 문자열에서 한 글자 씩 변경하여 제공된 다른 문자열로 바꾸고,

이 과정을 목표 문자열까지 반복하는 문제이다. 

 

풀이 과정은 다음과 같다.

1. 모든 문자열들을 문자 배열(char[])로 변경한다

2. 문자들에 대해 비교하며 dfs 과정을 진행한다

 

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    String[] words;
    char[][] wordChar;
    boolean[] visit;
    
    int answer = 51, wordCnt;
    String begin, target;
    
    public int solution(String begin, String target, String[] words) {
        
        this.begin = begin;
        this.target = target;
        
        wordCnt = words.length;
        visit = new boolean[wordCnt + 1];
        this.words = new String[wordCnt + 1];
        
        for (int i = 0; i < wordCnt; i++) {
            this.words[i] = words[i];
        }
        this.words[wordCnt] = begin;
        
        wordChar = new char[wordCnt + 1][];
        
        for (int i = 0; i < wordCnt; i++) {
            String word = words[i];
            wordChar[i] = word.toCharArray();
        }
        wordChar[wordCnt] = begin.toCharArray();
        
        visit[wordCnt] = true;
        
        dfs(0, wordCnt);
        
        return answer == 51 ? 0 : answer;
    }
    
    public void dfs(int depth, int curIdx) {
        
        String cur = words[curIdx];
        
        if (cur.equals(target)) {
            answer = Math.min(depth, answer);
            return;
        }
        
        if (depth == wordCnt) return;
        
        char[] str1 = wordChar[curIdx];
        
        for (int i = 0; i <= wordCnt; i++) {
            
            if (visit[i]) continue;
            int cnt = 0;
            char[] str2 = wordChar[i];
            
            for (int s = 0; s < str1.length; s++) {
                if (str1[s] != str2[s]) cnt++;
            }
            
            if (cnt != 1) continue;
            
            visit[i] = true;
            dfs(depth + 1, i);
            visit[i] = false;
        }
    }
}