🖊️ 문제

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

---

🖊️ 풀이

기본적으로 words에 있는 애들 중에서 cur과 비교해서
문자가 하나만 다른 애를 찾아서 바꿔주면 된다.

당연히 visited로 방문여부 체크해주고,,
words에 속한 단어들과 cur과 문자단위로 비교하면서
하나만 다른 애를 찾고,
걔를 큐에 넣어주면 된다잉.

최단거리인걸 알면서.. 괜히 DFS로 풀어서 오래걸렸던 문제 ㅜㅜ
그래도 둘의 차이점과 구조를 좀 확실히 알겠다
역시 삽질이 답!!

BFS

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

using namespace std;

bool visited[51] = {false,};

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    // 최종 단어가 없을 때 칼차단
    if (find(words.begin(), words.end(), target) == words.end()) 
        return answer;
    
    queue<pair<string, int>> q;		
    q.push(make_pair(begin, 0));
    
    while(!q.empty()) {
        string cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        for(int i = 0 ; i < words.size() ; i++) {
            if (visited[i]) continue;
            int diff = 0;
            for(int j = 0 ; j < cur.length() ; j++) {
                if (cur[j] != words[i][j])
                    diff++;
            }
            if (diff != 1) continue;
            visited[i] = true;
            cout << words[i] << cnt << endl;
            if (words[i] == target)
                return cnt + 1;
            else {
                answer++;
                q.push(make_pair(words[i], cnt+1));
            }
        }
    }
    
    return answer;
}

이렇게 된다.

만약 큐에 pair로 안넣어주고 그냥 string만 넣게 되면
depth가 무조건 증가하게 된다.
탐색은 하더라도,
target에 가깝게 변환하는 과정을 cnt(pair의 second)에 담아준다
그래서 그걸 queue에 같이 넣었다 빼다 하면서
탐색 깊이를 넣어줘야 한다.

위 탐색 예시를 보면 딱 이해가 갈듯 !!

DFS (틀림)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int total = 0;
bool visited[51] = {false,};

void DFS(string cur, string target, vector<string>& vec)
{
    if (cur == target) {
        return;
    }
    
 	for(int i = 0 ; i < vec.size() ; i++) {
        if (visited[i]) continue;
        int diff = 0;
        for(int j = 0 ; j < cur.length() ; j++) {
            if (cur[j] != vec[i][j])
                diff++;
        }
        if (diff != 1) continue;
        visited[i] = true;
        cout << vec[i] << endl;
        total++;
        DFS(vec[i], target, vec);
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    // 최종 단어가 없을 때 칼차단
    if (find(words.begin(), words.end(), target) == words.end()) 
        return answer;
    
    DFS(begin, target, words);
    answer = total;
    
    return answer;
}

DFS니까 역시나 최단거리가 안나온다.
연습삼아 DFS도 ~