99클럽 코테 스터디 14일차 TIL - DFS/BFS

항해99 코테 스터디 14일차 문제인 프로그래머스의 '단어 변환'은 시작 단어를 주어진 단어들로 변환하여 타겟 단어로 변환하는 최소 횟수를 구하는 문제다. 난이도는 레벨3이며 DFS나 BFS를 통해 해결할 수 있다.

 

오늘의 문제 - 단어 변환 문제 정보

문제 키워드

- DFS/BFS

난이도

- Level 3

 

문제 요약

• 시작 단어 begin과 목표 단어 target, 및 변환 가능한 단어의 목록 words가 주어진다.
• 단어 변환은 길이가 같은 두 단어가 딱 한글자만 다를 때, 변환할 수 있다.
  • ex) log -> lot, lot -> lat
• begin에서 target으로 변환하는 최소 변환 횟수를 구하여라.

 

문제 풀이 과정  

• 단어가 최대 50개이므로 변환되는 모든 경우의 수를 확인하여 문제를 풀 수 있다. (그래프 탐색 이용)
• 따라서 먼저 단어끼리 서러 변환 가능한지를 확인하고 이에 대한 인접 리스트를 구축하였다.
• DFS 또는 BFS를 이용하여 시작 단어를 목표 단어로 변환하기까지 그래프를 탐색한다.
  • 최소 횟수를 구하는 것이므로 BFS를 이용하는 것이 더 빠르게 탐색을 종료할 수 있다.
  • 그렇지만 DFS로 풀어도 시간이 충분하기 때문에 DFS로 구현해보았다.

코드

import java.util.*;

class Solution {
    
    Map<String, List<String>> adjMap = new HashMap<>();
    Map<String, Boolean> visited = new HashMap<>();
    int answer = 100;
    
    public int solution(String begin, String target, String[] words) {

        // 타겟이 words에 없는 경우 0 반환
        if (!Arrays.asList(words).contains(target)) {
            return 0;
        }
        
        int N = words.length;
        for(int i=0; i<N; i++) {
            adjMap.put(words[i], new ArrayList<>());
            visited.put(words[i], false);
        }
        
        // 각 단어들끼리 서로 변환 가능한지 확인하고 인접 리스트 맵 만들기
        for(int i=0; i<N-1; i++) {
            String wi = words[i];
            for (int j=i+1; j<N; j++) {
                String wj = words[j];
                if(canChange(wi, wj)) {
                    adjMap.get(wi).add(wj);
                    adjMap.get(wj).add(wi);
                }
            }
        }
        
        // begin에 대해 인접 리스트 맵 정보 추가
        adjMap.put(begin, new ArrayList<>());
        for (int i=0; i<N; i++) {
            String w = words[i];
            if(canChange(begin, w)) {
                adjMap.get(begin).add(w);
            }
        }
        
        dfs(begin, target, 0);
        
        return answer != 100? answer : 0;
    }
    
    // 길이가 같은 두 단어가 딱 한글자만 다를 때 true 반환
    private boolean canChange(String w1, String w2) {
        int len = w1.length();
        int diff = 0;
        
        for(int i=0; i<len; i++) {
            char c1 = w1.charAt(i);
            char c2 = w2.charAt(i);
            if(c1 != c2) {
                diff++;
            }
        }
        
        return diff == 1;
    }
    
    // 방문하지 않은 인접한 단어를 방문하는 DFS 메서드
    private void dfs(String here, String target, int cnt) {
        if (here.equals(target)) {
            answer = Integer.min(answer, cnt);
            return;
        }
        
        for(String next: adjMap.get(here)) {
            if (!visited.get(next)) {
                visited.put(next, true);
                dfs(next, target, cnt+1);
                visited.put(next, false);
            }
        }
    }
}

• 시간복잡도: O(N^2)
• 공간복잡도: O(N^2)

 

오늘의 학습 회고

새롭게 알게된 것

• 최소값, 최단거리 등을 구하는 경우에는 BFS를 우선적으로 떠올려보자.