[프로그래머스] 단어 변환 (07.13)

문제

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

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

 

접근법

먼저 당연히 DFS 일거라고 생각하고 풀었다.

백트래킹을 통해서 모든 배열을 확인하고, target에 도달할 때마다의 cnt 값들 중 최소값을 최종 결과로 리턴하였다.

다 풀고 다른 사람들의 풀이를 보는데 대부분의 사람들이 BFS로 풀었다.

그래서 나도 BFS로도 다시 풀어보았다.

방법은 비슷하였다.

 

코드

import java.util.*;

class Solution {
    private int min = Integer.MAX_VALUE;
    private String target;
    private boolean visited[];
    private String words[]; 

    public int solution(String begin, String target, String[] words) {

        if(!Arrays.asList(words).contains(target))
            return 0;

        this.target = target;
        this.visited = new boolean[words.length];
        this.words = new String[words.length];

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

        return bfs(begin);

        //dfs(begin, 0);

        //return min;
    }

    //BFS
    private int bfs(String begin){
        Queue<String> q = new LinkedList<>();
        q.offer(begin);

        Map<String, Integer> map = new HashMap<>();
        map.put(begin, 0);
        for(String word : words){
            map.put(word, 0);
        }

        while(!q.isEmpty()) {

            String poll = q.poll();
            if (poll.equals(target))
                return map.get(poll);

            for (int i = 0; i < words.length; i++) {
                if (!visited[i] && isPossible(poll, words[i])) {
                    q.offer(words[i]);
                    visited[i] = true;
                    map.put(words[i], map.get(poll) + 1);
                }
            }
        }

        return 0;
    }

    //DFS
    private void dfs(String str, int cnt) {
        if(str.equals(target)){
            min = Math.min(min, cnt);
            return;
        }

        for(int i=0;i<visited.length;i++){
            if(visited[i] || !isPossible(str, words[i]))
                continue;
            visited[i] = true;
            dfs(words[i], cnt+1);
            visited[i] = false;
        }

    }

    //변환 가능성을 판별하는 메소드
    private boolean isPossible(String str1, String str2){
        int cnt = 0;
        for(int i=0;i<str1.length();i++){
            if(str1.charAt(i) != str2.charAt(i))
                cnt++;
        }

        if(cnt == 1)
            return true;
        return false;
    }
}