문제 구성 📖

코딩테스트 사이트 : 프로그래머스
난이도 : 3단계
풀이 날짜 : 2022.07.01
사용한 풀이 방법 : BFS

문제링크

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

풀이법

두개의 단어가 주어지고, String[] 인 words가 주어진다. 한개의 단어가 다른 단어로 변환을 해야하는데, 가장 짧은 변환 과정을 찾아야한다.

• 문제를 맞닥뜨리자마자 BFS를 사용해야함을 느꼈다.
• 한번에 비용1을 소모해서, 변환하는 것이기 때문에, 딱 BFS가 적당했다.

제한 조건

• 한번에 한개의 알파벳만 바꿀수 있다.
• words에 있는 단어로만 변환 할 수 있다 .

필요한 기능

• 두 단어를 비교하여 단어 변환이 가능한지 유무
• 단어 하나를 꺼내어, 중복되지않게, target 단어까지 탐색하기

  코드

  
  import java.util.*;
  class Solution {
     static String t;
     static String[] arr; 
     static int result = 0;
     public int solution(String begin, String target, String[] words) {
         
         t = target;
         arr = words;
         int[] visited = new int[words.length];
         BFS(visited, begin, 0);
         return result;
     }
     public void BFS(int[] visited,String begin, int beforelocatiocn){
         HashMap<String,Integer> map = new HashMap<>();
         Queue<HashMap<String,Integer>> queue = new LinkedList<>(); 
         map.put(begin, beforelocatiocn);
         queue.add(map);
         
         while(!queue.isEmpty()){
             map = queue.poll();
             Map.Entry<String,Integer> entry = map.entrySet().iterator().next();
             if(entry.getKey().equals(t)){
                 result = entry.getValue(); 
                 return;
             }
             
             for(int i= 0; i<arr.length; i++){
                 if(visited[i] == 0){ //방문한적 없으면
                     if(changString(entry.getKey(),arr[i])){ //한글자 변환이 가능하다면
                         visited[i] = entry.getValue() + 1;
                         map = new HashMap<>();
                         map.put(arr[i], visited[i]);
                         queue.add(map);
                     }         
                 }
             }
         }
         
         return; 
     }
     
     public boolean changString(String origin, String diff){
         int count = 0;
         for(int i =0; i< origin.length(); i++){
             if(origin.charAt(i) != diff.charAt(i)){
                 count++;
             }
             if(count > 1){return false;}
         }
         if(count == 1) return true;
         return false;
     }    
  }
  

• 고정되어 버리는 값들은 Static전역변수로 고정시켜주고, BFS안에서 변환하는 값만 넣어 주었다.
• 여기서 BFS탐색을 하기위해, Queue<> 인터페이스를 사용해야되는데, 몇단계를 거쳐 변환했는지 기록을 queue안에 같이 넣어줘야되는 이슈가 발생했다.
• 처음엔 내부 Class를 만들어 처리할까 하다가, 기존의 자료구조로도 가능할 것 같아 HashMap을 사용하여 풀었다.

다른 사람과 비교하기

• 내가 고민했었던 것처럼, Queue<>의 타입을 static 내부 class로 만들어줘서 해결한 사람이 있었다.

      static class Node {
         String next;
         int edge;
  
         public Node(String next, int edge) {
             this.next = next;
             this.edge = edge;
         }
     }

• 위 class를 사용하게 되면 확실히 코드가 깔끔해진다.

  

• 테스트 통과 속도 전체적으로 느려졌지만, 그렇게 차이가 나진 않는다.

• 아마 매번 새로운class를 만들어 주는것과, 자료구조인 HashMap<>을 만들어주는 것의 차이인듯 싶다.