Today I Learned

오늘은 BFS 문제 하나를 풀어봤다.

단어변환(BFS)

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

• 문제
  시작단어와 target 단어가 주어진다. 시작단어는 String 배열 words에 있는 단어들 중에서 한 글자씩만 바뀔 수 있고 바뀔때 마다 단계가 추가된다. 최소 몇 단계를 거쳐야 시작 단어가 타겟단어로 바뀔 수 있는지 구하라.

• 구현 과정

1. 최소 단계를 구하는 문제이기 때문에 bfs로 단계를 하나하나 늘려가면서 답이 나오면 즉시 종료하는 식으로 풀면 될 것 같았다.

2. 우선 bfs로 구성하기 위해 간선을 만들어야 했는데 편의를 위해 인접리스트로 구성하고, 이중 리스트 안에 String 값으로 단어를 넣을지 아니면 단어의 words상 index 위치를 넣을 지 고민하다가 후자로 결정했다. 어차피 words 배열은 변하지 않기 때문에 이게 더 편할거라고 생각했다.

3. 우선 private 메서드로 1글자가 다를 경우를 검사하는 메서드를 간단하게 만들었다. charAt(i)를 for문으로 돌려 같은 위치의 글자가 다르면 카운트를 올리고 1일때만 true가 되게 했다. 1이상이면 바로 false를 중간에 반환해 연산을 줄였다.

4. 구현 도중 begin 단어가 words 배열안에 들어있다고 착각을 해서 시간을 좀 날려 먹었다. 문제를 좀 꼼꼼하게 읽고 넘어가야겠다.. 그래서 begin 단어는 그냥 가장 마지막에 간선정보를 추가하는 식으로 구현했다. 이미 앞쪽은 index가 오차없이 맞춰져 있기 때문에 이게 가장 편했다.

5. bfs 코드는 큐에 {해당 단어의 words 배열 상 인덱스, 깊이(단계)}의 크기 2짜리 int 배열을 넣는 식으로 구성했다. 그래서 사용 하지 않은 단어를 탐색할 때 target이면 단계 하나 늘려서 반환, 아니면 큐에 한단계 늘려서 삽입하는 방식으로 큐가 빌 때 까지 while문을 돌려 구현했다.

6. 큐의 구현체는 저번처럼 LinkedList가 아닌 ArrayDeque을 사용했다. 이에 대한 자세한 내용은 추후 TIL에 정리해보려 한다.

• 최종 코드

import java.util.*;
class Solution {
    private static List<List<Integer>> graph;
    private static boolean[] used;
    
    private static int bfs(String begin, String target, String[] words){
        int depth = 0;
        // 큐에는 (단어의 배열 상 index, 깊이(단계))의 크기 2의 int 배열을 넣는다.
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{words.length, depth});
        used[words.length] = true;
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int tmpI = tmp[0];
            int tmpD = tmp[1];
            
            for(int i : graph.get(tmpI)){
                if(!used[i]){
                    if(words[i].equals(target)){
                        return tmpD+1;
                    }
                    used[i] = true;
                    q.add(new int[]{i, tmpD+1});
                }
            }
            
        }
        
        return 0;
        
    } 
    
    private static boolean checkString(String a, String b){
        int difference = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) {
                difference++;
            }
            if (difference > 1) return false;
        }
        if (difference == 1) {
            return true;
            } else {
            return false;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        used = new boolean[words.length+1];
        graph = new ArrayList<>();
        
        // 간선 생성
        for(int i=0; i<words.length; i++){
            graph.add(new ArrayList<>());
            
            for(int j=0; j<words.length; j++){
                if (i==j) continue;
                boolean flag = checkString(words[i], words[j]);
                if (flag) {
                    graph.get(i).add(j);
                }
            }
        }
        graph.add(new ArrayList<>());
        for(int j=0; j<words.length; j++){
                boolean flag = checkString(begin, words[j]);
                if (flag) {
                    graph.get(words.length).add(j);
                }
            }
        
        
        return bfs(begin, target, words);
    }
}

• 중간에 문제 잘못 읽은 실수 때문에 begin 단어의 간선들을 처리한다고 코드가 좀 지저분해졌다. 로직에 큰 차이는 없지만 가독성이 다소 나빠진 듯 하다. 앞으로는 문제 잘 읽고 이해한채로 풀어야겠다.