[코딩테스트] Java 단어변환

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

dfs를 통해 모든 케이스를 돌면서 단어 변환이 되는지 체크하는 문제였습니다.

소스코드

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;
    
    // s1에서 s2로 가능한지.
    public boolean canChange(String s1, String s2) {
        int dif_cnt =0;

        for(int i = 0; i < s1.length(); i++){
          if(s1.charAt(i) != s2.charAt(i)){
            dif_cnt++;
          }
        }
        // 다른 문자가 1개일때
        if(dif_cnt == 1){
          return true;
        }
        // 다른문자가 한개가 아닐때
        return false;
    }
             
    public void dfs(String begin, String target, String[] words, int cnt) {
        if(begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            if(canChange(begin, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, cnt+1);
                visited[i] = false;
            }
        }
    }
      
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        
        if(answer == Integer.MAX_VALUE) {
            answer = 0;
        }
        
        return answer;
    }
}

코드 설명

• 전역변수
  • visited: 방문한 인덱스 확인
  • answer: target으로 변화 가능한 최솟값 저장.

// s1에서 s2로 가능한지.
public boolean canChange(String s1, String s2) {
    int dif_cnt =0;

    for(int i = 0; i < s1.length(); i++){
      if(s1.charAt(i) != s2.charAt(i)){
        dif_cnt++;
      }
    }
    // 다른 문자가 1개일때
    if(dif_cnt == 1){
      return true;
    }
    // 다른문자가 한개가 아닐때
    return false;
}

• canChange 메소드
  s1에서 s2로 이동이 가능한지(알파벳이 하나만 다른지) 확인하는 함수입니다.

public void dfs(String begin, String target, String[] words, int cnt) {
    if(begin.equals(target)) {
        answer = Math.min(answer, cnt);
        return;
    }

    for (int i = 0; i < words.length; i++) {
        if (visited[i]) {
            continue;
        }

        if(canChange(begin, words[i])) {
            visited[i] = true;
            dfs(words[i], target, words, cnt+1);
            visited[i] = false;
        }
    }
}

• dfs 메소드
  현재 값이 target과 같으면 answer를 업데이트 하고 종료합니다.
  • 방문한 인덱스면 반복을 계속하며, 단어 변환이 가능하면 업데이트합니다.
• answer가 Integer.MAX_VALUE면 0을 반환, 이외면 answer를 반환합니다.