https://programmers.co.kr/learn/courses/30/lessons/43163
해당 문제는 DFS로 해결하였다.
기본적인 DFS였으나 그냥 DFS를 돌리면 터져버린다.
그래서 백트랙킹을 통해서 해결해야 하는데, 이 때 조건은 문자열이 하나가 차이나야 한다는 조건이다.
문자열이 하나가 다를 때 다시 탐색할 수 있다. 문자열이 하나가 다른 조건을 찾을 때 끝까지 다 찾으면 시간복잡도의 측면에서 부하를 줄 수 있으므로 문자열 비교시에 2개 이상이 차이나면 비교를 그만하고 넘어가도록 해야 한다.
추가로, 해당 문제에서 words에 있는 단어들을 한 번만 사용해야한다는 조건이 따로 안주어져 있어서 처음에는 문제를 이해하지 못했다. 어쩌면 너무나 당연한 것이라 생각하여 따로 명시를 하지 않았던 게 아닐까 생각한다.
어쨋든 words의 단어들을 한 번만 사용해야 한다는 조건에 맞춰 vector<bool> check를 통해 탐색한 단어들은 재탐색하지 않도록 처리할 수 있다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ans_glb = 51;
vector<bool> check;
void dfs(vector<string> words, string now, string target, int cnt){
// 완성 비교
if(now.compare(target) == 0){
ans_glb = min(ans_glb, cnt); // 최소값 넣기
return;
}
// 갈 수 있는 곳 가기(한개 차이 나면 들어가기)
for(int i=0;i<words.size();i++){
// 문자열의 차이가 하나면 변경 가능
int diff = 0;
// 한번만 사용
if(check[i] ==true)
continue;
for(int j=0; diff<=1 && j<now.size();j++){
if(now[j] != words[i][j])
diff++;
}
// 하나만 차이나면 변경
if(diff ==1){
check[i] = true; // 탐색
dfs(words, words[i], target, cnt+1);
check[i] = false; // 탐색 끝
}
}
}
int solution(string begin, string target, vector<string> words) {
// 결과 도출 불가
if(find(words.begin(), words.end(), target) == words.end())
return 0;
check.assign(words.size(), false);
dfs(words, begin, target, 0);
// 답을 찾지 못하면
if(ans_glb == 51)
return 0;
// 정답 도출 성공
return ans_glb;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
프로그래머스_여행경로 (0) | 2019.11.17 |
---|---|
프로그래머스_디스크 컨트롤러 (0) | 2019.11.17 |
프로그래머스_ 정수 삼각형 (0) | 2019.11.17 |
프로그래머스_단속카메라 (0) | 2019.11.17 |
프로그래머스_타일 장식물 (0) | 2019.11.16 |