[level 3] 단어 변환

문제 해설 및 주의사항

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

---

 

풀이

1. 문제 파악

- 최단 거리 / 가중치 1 / 명확한 정점 선언 : bfs 최단 거리 문제이다.

 

- 정점 : i (words 안의 i 번째 string 의 index)

2. bfs 를 실행하기 위한 준비물

- 인접 리스트가 필요하다.

 

a. begin 부터 target 까지 가야한다. words 의 맨 처음 index 에 begin 을 삽입하자.

0. words 안에 target 이 없으면 0을 바로 반환

b. 인접 리스트를 생성하자.

b-1. words 를 순회하는데, from string 과 to string 을 비교하여 char 가 한 개만 다른 것을 인접 리스트에 삽입한다.

b-2. 주의해야 할 점은, from 과 to 를 비교할 때, 동일한 index 상의 char 를 비교해야한다는 점이다.

c. b 에서 만들어낸 인접 리스트를 가지고, 일반적인 bfs 를 시행한다.

---

풀이코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> adj_list[52];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    // words 의 0번째 idx 에 begin 을 넣어 bfs 하기 위해 insert
    words.insert(words.begin(), begin);
    
    // words 벡터 안에 target 이 없으면 0
    int ans_idx = -1;
    for(int i = 0 ; i < words.size(); i++){
        if(words[i].compare(target) == 0){
            ans_idx = i;            
            break;
        }
    }
    if(ans_idx == -1) return 0;
  
    // 인접 리스트 생성
        for(int i = 0; i < words.size(); i++){
            for(int j = i + 1; j < words.size(); j++){
                string from = words[i];
                string to = words[j];
                // 같으면 생략
                if(from.compare(to) == 0) continue;

                int count = 0;
                for(int cmp_index = 0; cmp_index < from.size(); cmp_index++){
                    if(from[cmp_index] != to[cmp_index]){
                        count++;
                    }
                    if(count > 1){
                        count = -1;
                        break;
                    }
                }
                if(count == 1){
                    adj_list[i].push_back(j);
                    adj_list[j].push_back(i);
                }
            }
        }
    
    // bfs
    int dist[52];
    fill_n(dist, 52, -1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    
    while(!q.empty()){
        int current_node = q.front(); q.pop();
        
        for(int i = 0; i < adj_list[current_node].size(); i++){
            int next_node = adj_list[current_node][i];
            
            // 미 방문 노드에만 시행
            if(dist[next_node] == -1){
                q.push(next_node);
                dist[next_node] = dist[current_node] + 1;    
            }
        }
    }
    
    answer = dist[ans_idx];
    if(answer == -1) answer = 0;
    
    return answer;
}

 

---

퇴고