[DFS/BFS] 단어 변환

yyeahh·2020년 8월 29일
0

프로그래머스

목록 보기
17/35
post-thumbnail

|| 문제설명 ||

  1. 두 개의 단어 begin, target과 단어의 집합 words가 있다.
  2. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 한다.
    • 한 번에 한 개의 알파벳만 바꿀 수 있다.
    • words에 있는 단어로만 변환할 수 있다.
  3. 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성하라.
  • begin : 시작 단어
  • target : 마지막 단어
  • words : 단어의 집합
_ 각 단어 : 알파벳 소문자
_ 각 단어의 길이 : 3 이상 10 이하, 모든 단어의 길이는 같다
_ words : 3개 이상 50개 이하의 단어, 중복X
_ begin != target
_ 변환할 수 없는 경우에는 0를 return

|| 문제해결방법 ||

- 각 단어의 자리를 비교해서 차이가 1 발생하는 단어들로만 재귀함수 호출
- 각 경우를 비교해서 가장 적은 과정을 return

|| 코드 ||

[2020.08.29] 실패
#include <string>
#include <vector>

using namespace std;

int answer = 100;

void dfs(string begin, string target, vector<int> chk, vector<string> words, int p) {
    for(int i=0; i<words.size(); i++) {
        int cnt = 0;	
        if(chk[i]){
            for(int j=0; j<words[0].size(); j++) {
                if(begin[j] != words[i][j]) cnt++;
            }
        }
        if(cnt == 1) {
            if(begin == target) {
                if(answer > p) answer = p;
                return;
            }
            chk[i] = 0;
            dfs(words[i], target, chk, words, p+1);
            chk[i] = 1;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<int> chk(words.size(), 1);
    
    dfs(begin, target, chk, words, 0);
    if (answer == 100) answer = 0;
    
    return answer;
}

  • if(begin == target) 의 위치 설정 오류
위치를 그대로 하려면 begin -> words[i]으로 바꾸고 p → p+1로 고쳐서 return 해야함

[2020.08.29] 성공
- 애초에 함수의 시작부분으로 옮겨 바로 return
#include <string>
#include <vector>

using namespace std;

int answer = 100;

void dfs(string begin, string target, vector<int> chk, vector<string> words, int p) {
    if(begin == target) {
        if(answer > p) answer = p;
        return;
    }
    for(int i = 0; i < words.size(); i++) {
        if(chk[i]){
            int cnt = 0;
            for(int j = 0; j < words[0].size(); j++) {
                if(begin[j] != words[i][j]) cnt++;
            }
            if(cnt == 1) {
                chk[i] = 0;
                dfs(words[i], target, chk, words, p+1);
                chk[i] = 1;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<int> chk(words.size(), 1);
    
    dfs(begin, target, chk, words, 0);
    if (answer == 100) answer = 0;
    
    return answer;
}

0개의 댓글