JArchive 프로그래밍 일기

문제 링크 

저번에 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;
}

문제 링크 

맞았습니다 코드 

#include <string>
#include <vector>
#include <queue>
using namespace std;

bool check[51]; // 확인 여부 

int solution(string begin, string target, vector<string> words) {
  int min_cnt = 1e9; // 최소 이동 횟수 
  int vector_size = words.size();
  int word_size = begin.size();

  queue<pair<int,string>> qu;
  qu.push({0, begin});

  while(!qu.empty()){
    int cnt = qu.front().first;
    string current_s = qu.front().second; // 비교 문자열
    qu.pop();

    for(int i = 0; i < vector_size; i++){
      // 이미 확인한 문자 지나감
      if(check[i]) continue;

      // 현재 문자열과 i번째 문자열이 1개만 다른지 확인
      int diff_cnt = 0;
      for(int d = 0; d < word_size; d++){
        if(words[i][d] != current_s[d]) diff_cnt++;
      }

      if(diff_cnt == 1){
        if(words[i] == target) { min_cnt = cnt + 1; break; } // 찾음
    
        qu.push({cnt+1, words[i]}); // 1개만 다르니까 여기로 이동 
        check[i] = true; // 이동했으니까 표시 
      }
    }
  }
  if(min_cnt == 1e9) min_cnt = 0;
  return min_cnt;
}