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

문제 URL

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

풀이

• 두 개의 단어 begin에서 target까지 최소 단계를 구하는 bfs문제다.

• 문제를 다 풀고 다른 풀이를 보았는데 dfs라고 푼것을 보았으나 사실상 브루트 포스로 푸는 것을 볼 수 있었다. 수강했던 백준강의에 따르면 dfs, bfs는 한번 방문했던 노드를 또 다시 방문하지 않아야한다!

• bfs로 각 단계마다(1,2,3,4….) 도달할 수 있는 모든 word를 queue에 넣는다. 따라서 한번 나왔던 단어는 다시 방문하지 않아도된다.(나중 단계에서 나오면 답이 될수 없기 때문이다 왜냐면 최소단계를 구하는 문제이기때문에!!)

나의 풀이 (배열)

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;


class Solution {
     public int solution(String begin, String target, String[] words) {
       //중복방문하지 않기위한 set
        HashSet<String> dupSet = new HashSet<>();

        //word 저장
        Queue<String> q = new LinkedList<>();
        //word의 단계저장
        Queue<Integer> nq = new LinkedList<>();
        //초기값 설정
        q.add(begin);
        nq.add(0);

        //bfs
        while(!q.isEmpty()){
            String str = q.remove();
            int n = nq.remove();

            for(String word : words){
                //중복검사
                if(dupSet.contains(word) || (!cal(word,str)))
                    continue;
                if(word.equals(target))
                    return (n+1);

                q.add(word);
                nq.add(n+1);
                dupSet.add(word);
            }
        }
        return 0;
    }

//한문자 빼고 맞는지 검사 맞으면 true
    public boolean cal(String word1, String word2){
        if(word1.length() != word2.length())
            return false;

        int n=0;
        for(int i=0; i<word1.length(); i++){
            if(word1.charAt(i) == word2.charAt(i))
                n++;
        }
        if(n==word1.length()-1)
            return true;
        return false;
    }
}