[프로그래머스 LV3] 단어 변환 (BFS, DFS) [C++, JAVA]

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 

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

단어 집합이 주어지고, 시작 단어에서 타깃 단어까지 몇 번만에 바꿀 수 있는지 리턴하는 문제이다.

그 대신, 단어는 한 글자만 바꿀 수 있다.

 

나는 처음에 DFS+백트래킹으로 단어의 문자 알파벳 하나하나를 바꿔가면서

ex) abc bbc cbc dbc ebc...

만약에 그 단어가 단어 집합에 있다면 방문 체크를 해주고 DFS를 하며 타깃을 방문하도록 구현을 했다.

하지만 매우 비효율적으로 코드를 구현한 것 같다..

 

다른 사람들의 풀이를 보니 알파벳 하나하나를 바꿀 필요 없이

한 글자만 바꿔서 다음 단어를 방문한다는 것은 두 단어끼리 다른 글자가 하나만 있으면 된다는 것이다.

굳이 완전 탐색처럼 알파벳을 모두 바꿀 필요는 없었다.

이후 최단거리를 구하므로 BFS 풀이를 확인할 수 있었다.

 

C++ 코드는 내가 DFS + 백트래킹으로 짠 것이고 자바 코드는 다른 사람의 풀이를 참고해서 나름대로 짜 본 코드이다.

 

<C++> - DFS 풀이

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

int ans = 987654321;
int ansFlag = false;
unordered_map<string, int> m;
int check[51];

void DFS(string begin, string target, int cnt){
    if(begin == target){
        if(ans > cnt){
            ans = cnt;
            ansFlag = true;
            return;
        }
    }
    for(int i = 0 ; i < begin.size() ; i++){
        for(int index = 0 ; index < 26 ; index++){
            begin[i] += 1;
            if(begin[i] == 'z'+1){
                begin[i] = 'a';
            }
            //cout<<begin<<"\n";
            if(m.find(begin) != m.end() && !check[m[begin]]){
                check[m[begin]] = true;
                DFS(begin, target, cnt+1);
                check[m[begin]] = false;
            }
        }
    }    
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    int i = 0;
    for(auto k : words){
        m[k] = i;
        i++;
    }
    if(m.find(target) == m.end())
        return answer;
    else
        DFS(begin, target, 0);
    if(ansFlag)
        answer = ans;
    return answer;
}

방문 체크를 위해 map을 이용해서 매핑하고, DFS+백트래킹을 해서 풀었다.

 

<JAVA> - BFS 풀이

import java.util.*;

class Node {
    String word;
    int num;
    
    Node(String word, int num){
        this.word = word;
        this.num = num;
    }
}

class Solution {
    boolean isComparable(String a, String b){
        int cnt = 0;
        
        for(int i = 0 ; i < a.length() ; i++){
            if(a.charAt(i) != b.charAt(i))
                cnt++;
        }
        if(cnt == 1)
            return true;
        else
            return false;
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean check[] = new boolean[51];
        Queue<Node> q = new LinkedList<>();
        
        q.add(new Node(begin, 0));
        
        while(!q.isEmpty()){
            Node cur = q.poll();
            String name = cur.word;
            int num = cur.num;
            
            
            if(name.equals(target)){
                answer = num;
                break;
            }
            
            for(int i = 0 ; i < words.length ; i++){
                if(check[i])
                    continue;
                if(isComparable(name, words[i])){
                    q.add(new Node(words[i], num+1));
                    check[i] = true;
                }
            }
        }
        return answer;
        
    }
}