[C++/PGS] Lv.3 : 단어 변환 (DFS/BFS/백트래킹) - 수정필요

깊이/너비 우선 탐색(DFS/BFS) : 단어 변환

문제 출처 - 프로그래머스 코딩테스트 고득점 Kit

 

문제 설명

두 개의 단어 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 합니다.

---

 

최소 변환 과정을 찾는거라서 BFS로 풀었습니다.

근데 이게.. 어찌어찌하다가 금방 해결하긴 했는데 왜 맞았는지 잘 모르겠음

그래서 코드 하나하나 뜯어볼 예정입니다

일단 코드 전체부터 ⬇️⬇️⬇️ (믿지마세요. 현재 테케 기준으로 통과는 되지만 정답 코드가 아닙니다...)

 

나의 풀이

(23년 5월 기준 업데이트)

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int answer = 0;
int visited[52] = {0,};

bool canChange(string a, int idx, vector<string> words){
    if(visited[idx]==1) return false;
    string tmp = words[idx];
    int re = 0;
    for(int i=0; i<tmp.length(); ++i){
        if(a[i]!=tmp[i]) re++;
    }
    if(re!=1) {return false;}
    return true;
}

bool bfs(string begin, string target, vector<string> words){
    queue<string> q;
    q.push(begin);
    while(!q.empty()){
        string a = q.front();
        q.pop();
        for(int i=0; i<words.size(); ++i){
            if(canChange(a, i, words)){
                q.push(words[i]);
                visited[i]=1;
                answer++;
                cout << words[i]<<" / ";
                if(words[i]==target) return true;
                break;
            }
        }
    }
    return false;
}

int solution(string begin, string target, vector<string> words) {
    if(find(words.begin(), words.end(), target)==words.end()){
        return 0;
    }
    sort(words.begin(), words.end());
    bool can = bfs(begin, target, words);
    if(!can) answer = 0;
    return answer;
}

---

분석 스타트

int solution(string begin, string target, vector<string> words) {
    if(find(words.begin(), words.end(), target)==words.end()){
        return 0;
    }
    sort(words.begin(), words.end());
    bfs(begin, target, words);
    return answer;
}

 

일단 main 부분입니다.

처음에 target이 words벡터에 아예 없으면 걸러버리고

있다면 bfs 함수로 진입합니다.

 

근데 여기서 words를 정렬해주면 풀리고 정렬 안하면 테케에서 틀림. why..?

( -> 정렬해줘야 순차적으로 변경되면서 답에 근접하는 것 같음)

 

void bfs(string begin, string target, vector<string> words){
    queue<string> q;
    q.push(begin);
    while(!q.empty()){
        string a = q.front();
        q.pop();
        for(int i=0; i<words.size(); ++i){
            if(canChange(a, i, words)){
                q.push(words[i]);
                visited[i]=1;
                answer++;
                if(words[i]==target) return;
                break; //?
            }
        }
    }
}

 

대망의 bfs입니다. 일단 queue 만들고 모든 원소를 순회하는 동안, 벡터 반복문 돌리는거까진 그냥 평범한 bfs네요

그리고 canChange 함수로

방문했던 스트링인지 , words[i] 와 a 가 문자 하나 차이인지 확인합니다.

그리고 조건문을 통과한다면 q.push를 해주겠죠

한 과정을 거치므로 answer++를 해줍니다

 

그리고 그냥 words[i]가 target과 같다면 그대로 return 해줍니다.

그릐고 여기서 한 과정을 거치면 break를 해줍니다. 여기서부터 이게 맞나?싶은데 혹시 이게 왜 되는지 아시는 분은 댓글 부탁드립니다....

break를 빼면 틀리더라고요. ;

(일단 모범답안은 dfs인 것 같음)

 

나름 백트래킹,,,이라고 생각하는데 테스트케이스가 5개밖에 없어서

그냥 운이 좋았던 것 같다.

나중에 다시 풀어봐ㅇㅑ지

 

<<<<< 설명해주실 알고리즘 천재 구합니다 >>>>>

 

이상. 끝