[프로그래머스] Lv2. 단어 변환(Java)

문제

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

프로그래머스

---

접근 방식

begin 에서부터 시작해서 target 까지 어떤 조건을 만족하는 단어들을 쭉 찾는다는 것에서 그래프 탐색 DFS or BFS라고 생각했다. target까지 쭉 하나의 줄기를 타고 찾기 때문에 DFS로 풀어야 하나 했는데, 그 단계의 최단 과정을 구하는 것이기 때문에 BFS 라고 생각했다.

• 최소한의 단계로 변환해야 하기 때문에 한번 사용한 단어는 사용할 수 없도록 하기 위해 방문처리 체크를 해야 한다.
• 단어를 바꿀 때는 words 배열 안에 있는 단어들 중 한 글자만 다른 단어로 바꿀 수 있기 때문에 두 단어가 한 글자만 다른지를 확인하는 함수가 필요하다.
• 현재 탐색중인 단어가 target과 같다면 원하는 값을 구한 것이기 때문에 종료하며 그 때까지의 변환 횟수를 return 한다.
• 만약 다 탐색했는데도 target을 찾지 못했다면 변환할 수 없는 것이기 때문에 0을 return 한다.

target이 words 배열에 포함되어 있지 않다면, 당연히 target으로 변환할 수 없기 때문에 이 경우에는 바로 0을 return 한다. target이 words 배열에 포함되어 있는지 확인한다.

---

문제 풀이

target이 words 배열에 포함되어 있는지 확인

가장 먼저 target이 words 배열에 포함되어 있어야만 target으로 변환할 수 있기 때문에, target이 words 배열에 포함되어 있는지를 확인하는 함수 isContain를 만들어준다.

boolean isContain(String s, String[] arr){
    for(int i=0; i<arr.length; i++){
        if(arr[i].equals(s)) return true;
    }
        
    return false;
}

isContain 함수로 target이 words 배열에 포함되는지 확인하고, 포함되어 있지 않다면 바로 0을 return 한다.

if(!isContain(target, words)){
    return 0;
}

// bfs 함수

---

두 문자열이 한 글자만 다른지 확인하는 함수

한 번에 한 개의 알파벳만 바꿀 수 있기 때문에 한 글자만 다른 문자열을 찾아야 한다.
두 문자열의 길이가 다르다면 당연히 한 글자만 변환하는 게 아니기 때문에 false를 return 한다.
두 문자열을 한 글자씩 순서대로 비교하면서 서로 다른 문자가 있다면 cnt 를 +1 해주고, cnt가 1이라면 한 글자만 다르다는 것이기 때문에 true를, 아니라면 false를 return 한다.

boolean isOnlyOneDiff(String a, String b){
	if(a.length() != b.length()){
        return false;
    }

    int cnt = 0;

    for(int i=0; i<a.length(); i++){
        if(a.charAt(i) != b.charAt(i)){
            cnt ++;
        }
    }

    return (cnt == 1) ? true : false;
}

---

BFS 함수

bfs를 구현하기 위해 큐를 하나 만든다. 이 큐에는 현재 탐색중인 단어가 들어가게 되는데, 현재 단어까지의 변환 횟수도 함께 저장하기 위해 객체를 만들어서 큐에 넣는다.
객체에는 String 단어 word와 그 단어까지의 변환 횟수인 int 형 cnt가 들어간다.

class Word{
    final String word;
    final int cnt;
        
    Word(String word, int cnt){
        this.word = word;
        this.cnt = cnt;
    }
}

단어들의 사용 여부를 체크하기 위해 arraylist 를 만들어서 사용하면 추가하고, 방문 여부를 확인하기 위해서는 contains 메소드로 arraylist에 포함되어 있는지를 확인했다.

 

처음 begin 단어부터, 변환 횟수는 처음이니까 0으로 시작한다.
words 배열을 돌면서 방문한 적이 없고 한 글자만 다른 단어라면 큐에 추가하고 방문처리 한다. 큐에 추가할 때는 다음 단어인 words[i], 해당 단어까지의 변환 횟수는 현재 단어까지의 변환 횟수에 + 1을 해서 큐에 추가한다.

 

만약 현재 단어가 target과 같다면 현재까지의 변환 횟수를 return 하고 함수를 끝낸다.
하지만 다 돌았는데도 target과 같지 않다면 target으로 변환할 수 없는 것이기 때문에 0을 return 한다.

int bfs(String[] words, String begin, String target){
    Queue<Word> q = new LinkedList<>();
    ArrayList<String> usedWords = new ArrayList<>();
    
    q.offer(new Word(begin, 0));
    usedWords.add(begin);
    
    while(!q.isEmpty()){
    	Word w = q.poll();
            
        if(w.word.equals(target)) return w.cnt;
            
        for(int i=0; i<words.length; i++){
            if(!usedWords.contains(words[i]) && isOnlyOneDiff(w.word, words[i])){
                q.offer(new Word(words[i], w.cnt + 1));
                usedWords.add(words[i]);
            }
        }
    }
        
    return 0;
        
}

---

전체 코드

import java.util.*;

class Solution {
    class Word{
        final String word;
        final int cnt;
        
        Word(String word, int cnt){
            this.word = word;
            this.cnt = cnt;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        if(!isContain(target, words)){
            return 0;
        }
        
        return bfs(words, begin, target);
    }
    
    int bfs(String[] words, String begin, String target){
        Queue<Word> q = new LinkedList<>();
        ArrayList<String> usedWords = new ArrayList<>();
        
        q.offer(new Word(begin, 0));
        usedWords.add(begin);
        
        while(!q.isEmpty()){
            Word w = q.poll();
            
            if(w.word.equals(target)) return w.cnt;
            
            for(int i=0; i<words.length; i++){
                if(!usedWords.contains(words[i]) && isOnlyOneDiff(w.word, words[i])){
                    q.offer(new Word(words[i], w.cnt + 1));
                    usedWords.add(words[i]);
                }
            }
        }
        
        return 0;
        
    }
    
    boolean isOnlyOneDiff(String a, String b){
        if(a.length() != b.length()){
            return false;
        }
        
        int cnt = 0;
        
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)){
                cnt ++;
            }
        }
        
        return (cnt == 1) ? true : false;
    }
    
    boolean isContain(String s, String[] arr){
        for(int i=0; i<arr.length; i++){
            if(arr[i].equals(s)) return true;
        }
        
        return false;
    }
}

---

처음에 dfs로 풀어야 할 것 같아서 최단 거리이지만 dfs로 도전했는데 백트래킹처럼 아닐 경우에는 빼고 다시 돌아오기(?)를 잘 못해서 bfs로 풀었다. dfs로도 풀 수 있을 것 같으니까 dfs로 다시 풀어보자!

그리고 기능을 함수 단위로 나눠서 쓰는 연습 & 객체를 사용하는 연습을 하는 중인데, 확실히 한 번에 쓸 때보다 메인 코드가 깔끔해지고 기능단위로 한눈에 보여서 좋은 것 같다. 사실 bfs는 굳이 함수로 따로 안하고 (재귀가 아니니까) 메인에서 해도 되지만 이게 깔끔해서 좋은 것 같다! 어떤 게 더 좋은 지 한번 찾아봐야지 ㅎㅎ