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

문제 링크 

 

저번에 BFS로 푼 것을 DFS로 다시 풀어봤다.

DFS는 재귀함수의 매개변수를 뭐로 할지와 종료조건이 중요하다. 

 

문제 설명에 '최소'라는 단어가 나오면 BFS 또는 이분탐색으로 풀 수 있는 가능성이 있다. 

DFS로 이 문제를 풀 땐 아무래도 단어목록을 매개변수로 넘겨야 하다보니 BFS가 더 직관적이었다. 

 

 

DFS로 푼 코드 

#include <bits/stdc++.h>
using namespace std;

string tg; // 목표
int answer = 50;  // 최소 횟수 저장
bool checked[52]; // 단어 확인 여부

bool diff_one(string cur, string w){// 단어 cur와 w를 비교 
  int diff_cnt = 0;
  for(int i = 0; i < w.size(); i++){
    if(cur[i] != w[i]) diff_cnt++;
  }
  return (diff_cnt == 1); // 1글자만 다른 단어라면 true 
}

void dfs(string s, vector<string> words, int cnt){

  if(answer <= cnt) return; // 백트래킹 
  if(s == tg) { 
    answer = min(cnt, answer); // 타겟 찾았다면 최소 횟수를 갱신하고 종료
    return;
  }

  int w_len = words.size();
  for(int i = 0; i < w_len; i++){
  
    if(diff_one(s, words[i]) && !checked[i]){ // 1글자만 다르고, 확인 안해본 단어라면 
      checked[i] = true;
      dfs(words[i], words, cnt + 1);
      checked[i] = false;
    }
  }
}

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

  tg = target; // 시작단어와 타겟단어 전역변수
  dfs(begin, words, 0); // begin 단어부터 탐색 시작 
  if(answer == 50) answer = 0; // 타겟 못찾음
  return answer;
}