99클럽 코테 스터디 33일차 TIL / [프로그래머스] 단어 변환

오늘의 학습 키워드

---

BFS

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 단어 변환
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    public int solution(String begin, String target, String[] words) {
        List<String> wordList = new ArrayList<>(Arrays.asList(words));
        wordList.add(begin);
        return bfs(target, wordList);
    }
    
    public int bfs(String target, List<String> wordList) {
        int answer = 0;
        boolean[] visited = new boolean[wordList.size()];
        Queue<Integer> queue = new LinkedList<>();
        visited[wordList.size() - 1] = true;
        queue.offer(wordList.size() - 1);
        
        while(!queue.isEmpty()) {
            answer++;
            int size = queue.size();
            for(int i=0; i<size; i++) {
                int idx = queue.poll();
                
                for(int j=0; j<wordList.size()-1; j++) {
                    if(!visited[j] && isDiffOnlyOneAlphabet(wordList.get(idx), wordList.get(j))) {
                        if(wordList.get(j).equals(target)) {
                            return answer;
                        }
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
        }
        
        return 0;
    }
    
    public boolean isDiffOnlyOneAlphabet(String begin, String target) {
        int p1 = 0;
        int p2 = 0;
        int diffCnt = 0;
        
        for(int i=0; i<begin.length(); i++) {
            if(begin.charAt(p1) != target.charAt(p2)) {
                diffCnt++;
                
                if(diffCnt > 1) {
                    return false;
                }
            }
            
            p1++;
            p2++;
        }
        
        return true;
    }
}

접근

• 간단한 BFS 구현 문제였습니다.
• 현재 단어와 다음 단어가 한 개의 알파벳 차이만 존재하는지 확인하고 만족한다면, Queue에 삽입합니다.

  public boolean isDiffOnlyOneAlphabet(String begin, String target) {
      int p1 = 0;
      int p2 = 0;
      int diffCnt = 0;
      
      for(int i=0; i<begin.length(); i++) {
          if(begin.charAt(p1) != target.charAt(p2)) {
              diffCnt++;
              
              if(diffCnt > 1) {
                  return false;
              }
          }
          
          p1++;
          p2++;
      }
      
      return true;
  }

  • 문제 조건에 의해 모든 단어의 길이는 같기 때문에, 위처럼 두 단어를 비교했습니다.
    - 앞에서부터 확인하면서 서로 다른 알파벳 개수가 2개 이상이 되면 false를 리턴하고, 그렇지 않으면 true를 리턴합니다.

    public int bfs(String target, List<String> wordList) {
        int answer = 0;
        boolean[] visited = new boolean[wordList.size()];
        Queue<Integer> queue = new LinkedList<>();
        visited[wordList.size() - 1] = true;
        queue.offer(wordList.size() - 1);
        
        while(!queue.isEmpty()) {
            answer++;
            int size = queue.size();
            for(int i=0; i<size; i++) {
                int idx = queue.poll();
                
                for(int j=0; j<wordList.size()-1; j++) {
                    if(!visited[j] && isDiffOnlyOneAlphabet(wordList.get(idx), wordList.get(j))) {
                        if(wordList.get(j).equals(target)) {
                            return answer;
                        }
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
        }
        
        return 0;
    }

  • Queue에는 words배열의 인덱스를 저장합니다. begin은 words 배열에 포함되어 있지 않으므로, 처음에 wordList라는 리스트를 만들어 words 배열의 값을 모두 복사하고, 마지막에 begin을 추가해서 관리했습니다.

소요 시간

30분