[Algorithm] 프로그래머스 C++ : 단어 변환

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

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

 

완전 헤맨 문제

 

dfs를 쓰는 것은 알았다

 

<삽질>

1. 테스트케이스가 다 3글자짜리 문자열이라서 1글자만 틀리다고 풀어야 될 거를 2글자가 맞다는 걸로 풀어버림 (이것때문에 몇시간 삽질)

2. dfs 재귀를 return 할때, answer=0이 되는 조건도 다 일일히 세서 return 조건을 주려고 함.

그냥 target일때 answer가 최소인지 확인만 하고 return 하면 되는데.. (테케5번을 계속 이것때문에 틀렸음)

 

 

+) is_possible과 a[][]를 안만들고, 그냥 dfs 함수에 begin을 넣고 그 다음 재귀에는 words[i]를 넣는 식으로 하면 코드가 훨씬 짧아진다.

나는 begin따로 그 이후부분 따로 이렇게 코딩해서 완전 더러운 코드

 

 

Code

#include <string>
#include <vector>
#include <iostream>
#include <string.h>

using namespace std;

int a[51][51];
int check[51];
int answer = 100;

bool is_possible(string a, string b) {
    int flag = 0;
    for(int i=0; i<a.size(); i++) {
        if(a[i]!=b[i]) {
            flag++;
        }
    }
    if(flag == 1) return true;
    return false;
}

void dfs(int idx, vector<string> words, string target, int dist) {
    if(words[idx]==target) {
        if(dist<answer) answer = dist;
        return;
    }
    
    for(int i=0; i<words.size(); i++) {
        if(check[i]==0 && a[idx][i] == 1) {
            check[i] = 1;
            dfs(i, words, target, dist+1);
            check[i] = 0;
        }
    }
}

int solution(string begin, string target, vector<string> words) {

    for(int i=0; i<words.size(); i++) {
        for(int j=0; j<words.size(); j++) {
            if(i==j) continue;
            if(is_possible(words[i], words[j])) {
                a[i][j] = 1;
            }
        }
    }
    
    for(int i=0; i<words.size(); i++) {
        if(is_possible(begin, words[i]) && check[i] == 0) {
            check[i] == 1;
            dfs(i, words, target, 1);
            check[i] == 0;
        }
    }
    
    if(answer==100) return 0;
    else return answer;
}