[Programmers] Level 3 : 단어 변환(Java)

문제 링크

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

프로그래머스

---

💡 풀이

단어를 변환하며 begin에서 시작해 target까지 도달할 수 있는 최단 거리를 구하는 문제입니다. 따라서, 다음과 같은 단계를 통해 문제를 해결했습니다.

1. 단어들이 있는 `words` 배열을 탐색하며 서로 변환 가능한 단어들 연결하기
   • 이때, 단어 변환이 가능한 경우는 1 글자만 다른 경우입니다. 
   • 이 조건을 이용해 서로 변환이 가능한지 확인한 뒤, 가능하다면 인덱스 번호로 단어를 연결합니다.
2. 연결된 단어들로 만들어진 최종 그래프를 BFS를 통해 begin에서 target까지의 최단거리 구하기

결국, 그래프를 만들고 BFS를 이용해 최단거리를 구하는 문제로 해석할 수 있습니다. 

그래프 만들기

우선, `words` 배열을 순회하며 변환 가능한 단어들을 확인하고, 가능하다면 연결시키는 부분을 구현합니다.

...
for(int i = 0; i < words.length - 1; i++) {
    String str1 = words[i];
    for(int j = i + 1; j < words.length; j++) {
        String str2 = words[j];
        if(checkStr(str1, str2)) {
            graph.get(i).add(j);
            graph.get(j).add(i);
        }
    }
}
...

boolean checkStr(String str1, String str2) {
    int count = 0;
    for(int i = 0; i < str1.length(); i++) {
        if(count >= 2) break;
        if(str1.charAt(i) != str2.charAt(i)) {
            count++;
        }
    }
    return count == 1 ? true : false;
}

`checkStr` 메서드에서는 각 자리의 문자를 확인해 같은 자리의 개수가 2 이상이라면 false를 리턴하도록 구현했습니다. 위의 `for` 문에서 이 `checkStr`이 반환하는 값이 true라면(연결 가능하다면) 두 인덱스를 그래프에서 연결합니다. 

 

BFS를 통한 최단 거리 구하기

위 과정을 통해 그래프가 만들어졌다면, 이를 이용해 BFS를 통해 최단 경로를 구합니다. 

int bfs(int start, String[] words, String target) {
    // init
    Queue<Integer> queue = new ArrayDeque<>();
    int[] distance = new int[words.length];
    boolean[] visited = new boolean[words.length];
    visited[start] = true;
    distance[start] = 0;
    queue.offer(start);

    int index = 0;
    boolean isFound = false;
    while(!queue.isEmpty()) {
        int cur = queue.poll();

        if(words[cur].equals(target)) {
            isFound = true;
            index = cur;
            break;
        }

        for(int next : graph.get(cur)) {
            if(visited[next]) continue;
            visited[next] = true;
            queue.offer(next);
            distance[next] = distance[cur] + 1;
        }
    }

    return isFound ? distance[index] + 1 : -1;
}

`bfs` 메서드의 인자 중 `start`는 시작하는 정점입니다. 이 정점은 begin에서 `words` 배열 중 갈 수 있는 모든 단어들이 됩니다. 

 

또한, 거리를 구하기 위해 start 정점에서 각 노드의 거리를 저장하고 있는 `distance` 배열을 선언해 연결된 그래프를 탐색할 때마다 업데이트하는 방식을 이용했습니다. 

 

만약, target과 일치하는 단어 없이 while문이 종료되었다면 도달할 수 없는 경우이기 때문에, `isFound` 변수를 사용해 단어를 찾아 종료한 경우와 찾지 못하고 종료한 경우를 구분했습니다. 이 결과에 따라 도달할 수 있다면 최단 거리를, 도달할 수 없다면 -1을 리턴하도록 구현했습니다.

전체 코드

전체적인 코드는 다음과 같습니다.  

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    
    public int solution(String begin, String target, String[] words) {        
        // init graph
        for(int i = 0; i < words.length; i++) {
            graph.add(new ArrayList<>());
        }
        for(int i = 0; i < words.length - 1; i++) {
            String str1 = words[i];
            for(int j = i + 1; j < words.length; j++) {
                String str2 = words[j];
                if(checkStr(str1, str2)) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }
        
        int answer = Integer.MAX_VALUE;
        for(int i = 0; i < words.length; i++) {
            if(checkStr(begin, words[i])) {
                int result = bfs(i, words, target);
                if(result != -1) {
                    answer = Math.min(answer, result);
                }
            }
        }
        
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    int bfs(int start, String[] words, String target) {
        // init
        Queue<Integer> queue = new ArrayDeque<>();
        int[] distance = new int[words.length];
        boolean[] visited = new boolean[words.length];
        visited[start] = true;
        distance[start] = 0;
        queue.offer(start);
        
        int index = 0;
        boolean isFound = false;
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            
            if(words[cur].equals(target)) {
                isFound = true;
                index = cur;
                break;
            }
            
            for(int next : graph.get(cur)) {
                if(visited[next]) continue;
                visited[next] = true;
                queue.offer(next);
                distance[next] = distance[cur] + 1;
            }
        }
        
        return isFound ? distance[index] + 1 : -1;
    }
    
    boolean checkStr(String str1, String str2) {
        int count = 0;
        for(int i = 0; i < str1.length(); i++) {
            if(count >= 2) break;
            if(str1.charAt(i) != str2.charAt(i)) {
                count++;
            }
        }
        return count == 1 ? true : false;
    }
}