단어 변환
-
두 개의 단어 begin(ex. hit) target(ex. cog)와 단어의 집합 words가 있다 (ex. hot,dot,dog,lot,log,cog)
-
begin 단어 부터 시작
-
한 번에 한 개의 알파벳만 바꿀 수 있다.
-
words에 있는 단어로만 바꿀 수 있다(임의로 못 바꾼다)
-
최소한으로 target으로 가는 과정을 만들어 보자 (여러가지 경로가 있을 수 있다)
-
모든 단어의 길이는 같습니다.
-
변환할 수 없는 경우에는 0을 return
-
자신이 갈 수 있는 경로 (단어가 1개 밖에 차이 안나는 경우) 에 대해서 모든 경우를 탐색 해 준다.
-
만약 자신이 방문하지 않았고, 갈 수 있는 경로라면 dfs!
-
target과 현재 자신이 같다면 return!
주의할 점
visited는 dfs 과정마다 다르게 사용되어야 하기 때문에
전역변수로 두지 않고, 파라미터로 끼워 넣어 줬다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int answer = 1e9;
bool isit(string now, string next) { // 1개 밖에 차이 안나는 지?
int ans = 0;
for (int i = 0; i < now.size(); i++) {
if (now[i] != next[i]) ans++;
}
return (ans == 1) ? true : false;
}
void go(vector<string> words, int index, int ans, string target,vector<bool>visited) {
visited[index] = true;
string now = words[index];
if (now == target) { // target이라면 최소한의 과정의 수로 만들어 주자
answer = min(answer, ans);
return;
}
for (int i = 0; i < words.size(); i++) {
if (!visited[i] && isit(now, words[i])) // 방문하지 않았고, 갈 수 있다면
go(words, i, ans + 1, target, visited);
}
return;
}
int solution(string begin, string target, vector<string> words) {
for (int i = 0; i < words.size(); i++) {
if (isit(begin, words[i])) {
vector<bool>visited;
visited.resize(51);
go(words, i, 1, target, visited);
}
}
return (answer == 1e9) ? 0 : answer;
}
