[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환 (Java)

프로그래머스 Level 3 깊이/너비 우선 탐색 - 단어 변환 (자바)

 

 

출처

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

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

 

 

 

문제

두 개의 단어 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 합니다.

 

 

 

 

 

입출력 예

입출력 예 1

 

 

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

 

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

 

접근 방법

1. target 문자가 words에 있지 않으면 연산이 불가능하기 때문에 test 메서드로 체크한다.

2. 있으면 vocas 길이만큼 반복문을 돌려 해당 원소의 문자와 begin을 비교해 틀린 값이 1개만 있는지 찾는다.

(나는 이 부분 때문에 계속 오류가 났었다..

같은 문자의 개수가 == 2 일 때로 처음에 해서 문제였다..

문제에서 문자의 길이가 3~10 이기 때문에  틀린 문자의 개수 == 1 일 때로 변경했더니 잘 되었다.)

3. dfs를 돌려 최단 경로를 찾는다.4. 해당 조건을 다 만족할 때 다음 문자를 매개변수로 넘겨줘 target을 만날 때까지 계속 탐색한다.

 

 

 

내 코드

import java.util.*;

class Solution {
    private static int n;
    private static String[] vocas;
    private static boolean[] visit;
    
    public int solution(String begin, String target, String[] words) {
        int answer = 10;
        
        vocas = words;
        visit = new boolean[words.length + 1];
        
        boolean flag = true;
        if (!test(target)) {
            answer = 0;
        } else {
            for (int i=0; i<vocas.length; i++) {
                if (check(begin, vocas[i])) {
                    //begin -> vocas[i] 변환 가능할 때 탐색 시작
                    Arrays.fill(visit, false);
                    //System.out.println(vocas[i]);
                    int result = dfs(i, vocas[i], target, 1);
                    answer = Math.min(answer, result);
                }
            }
        }
        
        
        return answer;
    }
    
    public int dfs(int start, String word, String target, int cnt) {
        
        if (word.equals(target)) {
            //탐색한 문자와 target이 같으면 끝낸다.
            return cnt;
        }
        
        if (visit[start]) {
            //방문처리 된곳을 찾아오면 다시 되돌려보낸다.
            return cnt;
        }
        
        //해당 원소 방문처리
        visit[start] = true;
        
        int num = 0;
        for (int i=0; i<vocas.length; i++) {
            if (i != start && !visit[i] && check(word, vocas[i])) {
                //방문 x
                //같은 문자 x
                //단어가 2개이상 같아야함
                //System.out.println("start :: " + start + " , i :: " + i + " , word :: " + word + " , vocas[i] :: " + vocas[i]);
                num = dfs(i, vocas[i], target, cnt+1);
            }
        }
        return num;
        
    }
    
    public boolean check(String str1, String str2) {
        
        int cnt = 0;
        for (int i=0; i<str1.length(); i++) {
            char c1 = str1.charAt(i);
            char c2 = str2.charAt(i);
            
            if (c1 != c2) cnt++;
        }
        
        if (cnt == 1) {
            return true;
        } else {
            return false;
        }
        
    }
    
    public boolean test(String target) {
        
        for (int i=0; i<vocas.length; i++) {
            if (target.equals(vocas[i])) {
                return true;
            }
        }
        return false;
    }
}

 

 

고려할 점

1. 문제 조건 꼼꼼히 읽을 것

2. dfs 활용할 것