[프로그래머스] 단어 변환 c++

 

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43163#

KEY

• 두 문자열의 요소가 1개만 다른지 확인하는 함수를 따로 작성했다.
• 처음에 방문 배열(visited)를 사용하지 않고 DFS로 풀이했는데, 테스트케이스 3번에서 시간초과가 발생했다.
• 결국 visited를 사용하여 방문했던 노드를 탐색하지 않는 과정을 추가

 

Code

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 51;
int answer = 999999999;
bool visited[MAX];
 
bool check(string s1, string s2){ //두 문자열의 요소가 1개만 다른지 판별하는 함수
    int diff = 0;
    for(int i=0;i<s1.size();i++){
        if(s1[i] != s2[i]){
            diff++;
        }
    }
    if(diff == 1){
        return true;
    }else{
        return false;
    }
}
void dfs(string s, string target, int cnt, vector<string> words){
    
    if(cnt == words.size()) //종료조건1: words배열을 다 돌았을 경우
        return;
    
    if(s == target){ //종료조건2: target에 도달했을 때
        answer = min(answer, cnt);
        return;
    }
    
    for(int i=0;i<words.size();i++){
        if(visited[i]) //방문했다면 넘어감
            continue;
        
        if(check(s,words[i])){ //방문하지 않고, 두 문자열의 요소가 1개만 다르다면
            visited[i] = true;
            dfs(words[i], target, cnt+1, words);
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    dfs(begin, target, 0, words);
    if(answer == 999999999)
        return 0;
    else
        return answer;
}