✅ 가장 중요한 키워드
가장 짧은 변환 과정
→ BFS 쓰자 !
한 개의 알파벳만 다른 경우를 Bool로 리턴하는 함수 만들자.
bool canSwitch(string s1, string s2) { }
맨 처음에 words에 target이 포함되어 있는지 확인하자.
[처음에 answer를 크게 선언하는 방법도 존재]
코드 짜자
// bfs(begin, target, words)
void bfs(string begin, string target, vector<string> words) {
queue<info> q;
// q({비교할 문자열, 변환 개수})
q.push({begin, 0});
while(!q.empty()) {
string cur = q.front().word;
answer = q.front().cnt;
q.pop();
for (int i = 0; i < words.size(); i++) {
if (canSwitch(cur, words[i])) { // 한 알파벳만 다를 경우, 수행
if (words[i] == target) { // target과 같을 경우, answer+1 하고 return
answer++;
break;
}
if (!check[i]) { // 아직 방문하지 않은 경우, q에 넣어줌
q.push({words[i], answer + 1});
check[i] = true;
}
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
bool check[51];
int answer;
struct info {
string word;
int cnt;
};
bool canSwitch(string s1, string s2) {
int cnt = 0;
for (int i = 0; i < s1.size(); i++) {
if (s1[i] != s2[i]) {
cnt++;
}
}
if (cnt == 1) {
return true;
} else {
return false;
}
}
void bfs(string begin, string target, vector<string> words) {
queue<info> q;
q.push({begin, 0});
while(!q.empty()) {
string cur = q.front().word;
answer = q.front().cnt;
q.pop();
for (int i = 0; i < words.size(); i++) {
if (canSwitch(cur, words[i])) {
if (words[i] == target) {
answer++;
break;
}
if (!check[i]) {
q.push({words[i], answer + 1});
check[i] = true;
}
}
}
}
}
int solution(string begin, string target, vector<string> words) {
bool isPossible = false;
for (int i = 0; i < words.size(); i++) {
if (words[i] == target) {
isPossible = true;
}
}
if (!isPossible) {
return 0;
}
bfs(begin, target, words);
return answer;
}