[Programmers] 깊이/너비 우선 탐색(DFS/BFS) - 단어변환

jiiiiinni·2022년 9월 23일
0

Algorithm&Coding-test

목록 보기
23/26
post-thumbnail

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

Problem

Code

import java.util.*;

class Solution {
    static int answer = Integer.MAX_VALUE;
    static int[] visited;
    
    public void DFS(int depth, String begin, String target, String[] words) {
        if (begin.equals(target)) {
            answer = Math.min(answer, depth);
        } else {
            for (int i=0; i<words.length; i++) {
                int cnt = 0;
                for (int j=0; j<words[i].length(); j++) {
                    if (begin.charAt(j) != words[i].charAt(j)) cnt++;
                }
                if (cnt == 1 && visited[i] == 0) {
                    visited[i] = 1;
                    DFS(depth+1, words[i], target, words);
                    visited[i] = 0;
                }
            }   
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        visited = new int[words.length];
        if (!Arrays.asList(words).contains(target)) answer = 0;
        else DFS(0, begin, target, words);
        return answer;
    }
}

Result

profile
꾸준히

0개의 댓글