[프로그래머스] [C++] [알고리즘]단어변환

프로그래머스의 DFS와 BFS 에있는 단어변환 level 3 문제임

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

이 문제 테스트케이스 상당히 이상합니다.
저도 코드 실행 예제 1번이 틀렸었는데 제출하면 통과되었어요.
다행히 조건 하나만 추가하니 예제도 통과했네여
같은 로직인데 같은 상황이 발생하시는 분은 한가지 생각해보세요
target에 도착했을 때 뎁스를 기록하고 return 하되 방문체크를 하면 안됩니다. visit 배열의 메모리 초기화는 처음에만 하기 때문에 중간뎁스부터 (정답으로 향하는) 경로가 나눠질 경우 때문입니다.

저는 dfs 로 풀었습니다.

기본적으로 단어끼리 비교해서 한자리만 틀린 단어인지 확인할 함수는
필수적으로 필요합니다.

bool compare(string a, string b) {
    int count = 0;
    for (int i = 0; i < a.length(); i++) {
        if (a[i] != b[i]) {
            count++;
        }
    }
    if (count == 1) return true;
    else return false;
}

이 후 로직을 생각합니다.

words 배열의 단어중에 begin 단어와 한자리만 다른 단어는
여러개가 있을 수 있습니다.

compare == true 인 단어에서 dfs 를 시작해서

target 단어를 만날때의 depth를 기록합니다.

하지만 다른 경로를 통해서 target 를 만날 확률 도 있습니다.

이 때 target에 도달했을 때의 depth를 최소값으로 업데이트합니다.

"hit" "cog" ["hot", "dot", "dog", "lit", "log", "lot", "cog"]

의 경우엔 hot 으로 출발할 수도 lit 으로 출발할 수도 있어요.

hit > lit > lot > log > dog > cog
hit > hot > dot > dog > cog

두 가지 모두 cog 에 도달하기 때문에 dfs 의 경우 최소 경로로 업데이트가 필요해요

depth를 기록할 배열(dep)을 만들고 index를 넘겨주어 target의 index에 depth를 기록, 업데이트 합니다.

아 그리고 target의 인덱스를 찾기 못했을 경우엔 0을 반환해버립니다.

정답코드

#include <string>
#include <vector>
#include <cstring>

using namespace std;

vector<string> v;
string b, t;
int dep[50] = {0,};
bool visit[50] = {0,};

bool compare(string a, string b) {
    int count = 0;
    for (int i = 0; i < a.length(); i++) {
        if (a[i] != b[i]) {
            count++;
        }
    }
    if (count == 1) return true;
    else return false;
}

void dfs(int n, string s, int index) {
    n++;
    
    if (t == s) {
        if (dep[index] == 0) {
            dep[index] = n;
        } else {
            dep[index] = dep[index] > n ? n : dep[index];
        }
        return;
    } else {
        visit[index] = true;
    }
    
    for (int i = 0; i < v.size(); i++) {
        if (compare(v[i], s) && !visit[i]) {
            
            dfs(n, v[i], i);
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    v = words;
    b = begin;
    t = target;
    
    int ansIndex = 51;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == t) {
            ansIndex = i;
            break;
        }
    }
    
    if (ansIndex == 51) return 0;
    
    for (int i = 0; i < words.size(); i++) {
        if (compare(begin, words[i])) {
            dfs(answer, words[i], i);
            memset(visit, false, sizeof(visit));
        }
    }
    
    return dep[ansIndex];
}