[프로그래머스 Level 3] [DFS/BFS] 단어 변환 (C++)

안녕하세요, 코딩하는 경제학도 쏘코입니다.

각종 과제와 수업의 늪에서 빠져나와 문제를 풀어보았습니다.

꾸준히 문제를 푸는 것이 굉장히 어려운 일이라는 것을 요새 절실히 깨닫고 있습니다.

안 풀다 푸니 너무 어려워 ~_~

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

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

programmers.co.kr

0. 문제 설명

두 개의 단어 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 함수를 작성해주세요.

0.0. 제한사항

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

0.1. 입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

0.2. 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

1. 풀이 과정

일반적인 경로찾기 문제와 다른 점은, begin이 words에 들어가있지 않다는 점입니다.

그래서 저는 맨 처음에 begin에서 연결된 친구들을 찾아서 queue에 넣는 것을 생각했습니다. (words에 begin을 넣어서 알고리즘을 구현하는 것도 가능합니다!)

그리고 dfs/bfs 중복처리 및 각 단어로 변경하는 데 몇 번의 과정이 필요한지를 담기 위해 map을 만들었습니다. int를 써도 되고(이 경우 index를 넣습니다) map을 써도 되는데 이번에는 map을 한번 써보고 싶어서.. map에 단어들을 담으면서, words에 타겟이 있는지 확인하고 타겟이 없으면 0을 return하도록 만들었습니다.

이제 큐에 첫 번째 친구들을 넣어줍니다. 원래라면 start부분을 넣어주고 거기서 연결된 친구들을 넣어줘야 하지만 위에서 말한 대로 begin이 words에 없으므로 따로 찾아서 넣어줍니다. begin과 words를 자릿수별로 비교해서 같은 위치에 같은 글자가 있다면 1씩 늘려줍니다. 이게 글자수-1만큼 되야 1글자만 다른 것이 되겠죠? 그런 친구들을 queue에 담아줍니다. 그리고 map에서 담은 친구들의 second값을 1로 바꿔줍니다.

추가로 바로 target단어로 바꿀 수 있다면 이 과정에서 1을 return하고 종료합니다.

그리고 다 비교했는데 queue에 아무것도 들어가있지 않으면 0을 return하고 종료합니다.(target으로 갈 수 없으므로)

2번째부터는 위의 작업의 반복입니다. 다만 맨 앞에서부터 하나씩 빼서 넣게 되겠죠. 그리고 비교할 때 map이 0인 친구들만 비교합니다. 이미 한번 방문한 단어는 다시 방문할 필요가 없기 때문이죠. 그리고 비교해서 변경할 수 있는 단어를 찾으면 이전 단어의 map값 + 1한 값을 map[바꿀단어]에 넣어줍니다. target로 변경이 가능하면, map[target]의 값을 반환해서 마칩니다.

만약 모든 작업을 끝내고도 target으로 가지 못한 상황이라면 begin에서 target으로 갈 수 없으니 0을 return합니다.

아래 소스코드에 자세하게 설명을 담겨놓았으니 참고하시면 좋을 것 같습니다 :)

2. 소스 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <map>

using namespace std;

int solution(string begin, string target, vector<string> words) {
    /*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n)
    사용한 알고리즘: BFS(너비 우선 탐색)
    사용한 자료구조: queue, map
    */

    int n = words.size(); // words의 크기
    bool chk1 = false; // words에 타겟이 있는지 체크용(false는 없음, true는 있음)
    map<string,int> m; // 방문한 곳 얼마만에 도달했는지 체크용
    queue<string> q; // 경로 저장용 큐
    for(int i = 0; i < n; ++i){ // target이 words에 있는지 확인
        m[words[i]] = 0; // map에 words들 넣어줌
        if(target == words[i]) // words에 타겟이 있는지 확인
            chk1 = true;
    }
    if(chk1 == false) // 타겟이 없다면
        return 0; // 0 리턴
    
    // 맨 처음 큐가 비어있으므로 시작단어로부터 바뀔 수 있는 단어를 큐에 넣어줌
    int ws = begin.size(); // word size
    int chk2; // 1글자만 다른지 확인하기 위한 변수
    for(int i = 0; i < n; ++i){
        chk2 = 0; // 매번 0으로 초기화해야함
        for(int j = 0; j < ws; ++j){
            if(begin[j] == words[i][j]){ // 시작단어와 words[i]를 비교해서 같은 위치에 같은 글자가 있다면
                ++chk2; // chk2를 1 늘려주기
            }
        }
        
        if (chk2 == ws-1){ // 만약 글자가 딱 1개만 다르면
            q.push(words[i]); // queue에 그 단어 넣어줌
            m[words[i]] = 1; // 맨 처음이니까 map에 1 넣어줌
            if (words[i] == target) // 바로 타겟단어라면
                return 1; // 1을 반환
        }
    }
    
    if (q.empty()) // 첫 작업을 마쳤는데 queue에 아무것도 없다?
        return 0; // 0을 반환
    

    // 2번째부터 반복진행
    string chkword; // queue에서 단어를 빼내는 용도로 사용할 string
    while(!q.empty()){ // queue가 빌 때까지 계속 진행 (BFS)   
        // queue에서 맨 앞 단어 뺌 
        chkword = q.front();
        q.pop();
        
        // 위에서와 같이 다시 체크
        for(int i = 0; i < n; ++i){
            chk2 = 0;
            if(m[words[i]] == 0){ // 아직 방문하지 않았다면 그때 체크
               for(int j = 0; j < ws; ++j){
                    if(chkword[j] == words[i][j]){ // 아까 뺀 단어와 words[i]를 비교해서 같은 위치에 같은 단어가 있다면
                        ++chk2; // chk2를 1 늘려줌
                    }
                }
                if (chk2 == ws-1){ // 딱 1개 차이나면
                    q.push(words[i]); // 큐에 넣음
                    m[words[i]] = m[chkword] + 1; // 이전 횟수에 + 1만큼을 체크용 map에 넣어줌
                    if (words[i] == target) // target이면 그대로 리턴
                        return m[words[i]];
                }  
            }
        }
    }
    
    return 0;
}