본문 바로가기

PS

[Programmers] LV3 - 단어 변환

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

 

코딩테스트 연습 - 단어 변환

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수

programmers.co.kr

 

 

 

문제 파악

 

문제에 나와 있듯이

1. 한 번에 한 개의 알파벳만 변환할 수 있다.

2. words 배열에 있는 단어로만 변환할 수 있다.

3. begin에서 target으로의 변환 할 때까지 걸린 횟수를 return 하고, 변환할 수 없을 경우 0을 return 해준다.

 

더보기
import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        boolean[] visited = new boolean[words.length];
        Queue<String> q = new LinkedList<>();

        q.add(begin);

        answer = dfs(q, visited, words, target, 0);

        return answer;
    }

    public int dfs(Queue<String> q, boolean[] visited, String[] words, String target, int depth)
    {
        int result = Integer.MAX_VALUE;
        while (!q.isEmpty())
        {
            int size = q.size();
            for (int sz = 0; sz < size; sz++) {
                String str = q.poll();
                if (str.equals(target)) {
                    return Math.min(result, depth);
                }

                char[] origin = str.toCharArray();
                for (int i = 0; i < words.length; i++) {
                    int cnt = 0;
                    char[] change = words[i].toCharArray();
                    for (int j = 0; j < change.length; j++) {
                        if (origin[j] != change[j]) {
                            cnt++;
                        }
                    }
                    if (cnt == 1 && !visited[i]) {
                        visited[i] = true;
                        q.add(words[i]);
                    }
                }
            }
            depth++;
        }
        return 0;
    }
}

 

'PS' 카테고리의 다른 글

[BOJ] 1865번 : 웜홀  (0) 2021.07.06
[BOJ]11404번 : 플로이드  (0) 2021.07.06
[Programmers] LV3 - 순위  (0) 2021.07.03
[Programmers] LV1 - 크레인 인형뽑기 게임  (0) 2021.07.02
[Programmers] LV2 - 짝지어 제거하기  (0) 2021.06.30