문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
| begin | target | words | return |
|---|---|---|---|
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
문제 요약:
begin 문자열을 한 문자씩 바꿔서 words 안의 문자열로 변화시키는 데 target문자열이 되도록 하려면 몇 단계를 거쳐야 하는지 찾기
생각할 점:
- 한 단계에 한 문자만 바뀐다.
- words 배열 안에 없는 단어로는 변환할 수 없다.
몇 단계 ? → begin 노드부터 target 노드까지 도달하는데 몇 개의 엣지가 필요한가
풀이 방법:
Q. words 문자열 벡터에서 한 글자만 다른 단어를 어떻게 찾을건가
- words 벡터에 대해 begin과 1글자만 다르면 변환 가능
Q. begin 문자열에서 target 문자열까지 가는 경로 찾기
- BFS 사용 ( 현재 문자열을 큐에 넣어서 이미 방문했는지 + 변환가능한 단어인지 검사)
- 인접여부 대신 변환 가능 여부(다음 순서로 올 수 있는가)
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<bool> visited(51, false);
// 현재 문자와 다음 문자가 변환 가능한지 체크하는 함수
bool changeable(string before, string after) {
int diff = 0;
for (int i = 0; i < before.size(); i++) {
if (before[i] != after[i])
diff++;
}
return diff == 1;
}
// BFS 함수
int BFS(const string& begin, const string& target, vector<string>& words) {
queue<pair<string, int>> q;
q.push({begin, 0});
while (!q.empty()) {
string node = q.front().first;
int index = q.front().second;
q.pop();
if (node == target)
return index;
for (int j = 0; j < words.size(); j++) {
if (!visited[j] && changeable(node, words[j])) {
q.push({words[j], index + 1});
visited[j] = true;
}
}
}
return 0; //도달하지 못하면 0반환
}
int solution(string begin, string target, vector<string> words) {
return BFS(begin, target, words);
}
큐 페어가 아닌 문자열 큐로 생성해서 한 단계 탐색이 끝나면 Index를 증가시키는 코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<bool> visited(51, false);
// 현재 문자와 다음 문자가 변환 가능한지 체크하는 함수
bool changeable(string before, string after) {
int diff = 0;
for (int i = 0; i < before.size(); i++) {
if (before[i] != after[i])
diff++;
}
return diff == 1;
}
// BFS 함수
int BFS(const string& begin, const string& target, vector<string>& words) {
queue<string> q;
q.push(begin);
int index = 0;
while (!q.empty()) {
for (int i = 0; i < q.size(); i++) { // 현재 단계의 단어들에 대해 탐색
string node = q.front();
q.pop();
if (node == target)
return index;
for (int j = 0; j < words.size(); j++) {
if (!visited[j] && changeable(node, words[j])) {
q.push(words[j]);
visited[j] = true;
}
}
}
index++; // 한 단계의 탐색이 끝났으므로 index를 증가시킴
}
return 0;
}
int solution(string begin, string target, vector<string> words) {
return BFS(begin, target, words);
}🌟 chageable
현재 문자열(노드) 이 다음 문자열로 변환될 수 있는지 확인하는 함수
- 한 문자만 다르고 전부 같아야한다.→ 다른 문자의 수를 diff 변수로 세서 다른 문자가 하나이면 true
//before : 현재 문자열, after: 다음 문자열
bool changeable(string before, string after) {
int diff = 0;
for (int i = 0; i < before.size(); i++) {
//문자 하나씩 비교해서 다르면 다른 문자 수 세기
if (before[i] != after[i])
diff++;
}//1개면 변환 가능 -> true
return diff == 1;
}🌟BFS
int BFS(const string& begin, const string& target, vector<string>& words) {
//검색할 문자열들을 담을 큐 q
queue<string> q;
//첫번째 문자 begin을 큐에 추가
q.push(begin);
int index = 0;
while (!q.empty()) {
//큐에 있는 문자열들을 큐에 맨 앞에 있는 문자열을 빼서 BFS 검사
for (int i = 0; i < q.size(); i++) { // 현재 단계의 단어들에 대해 탐색
//현재 검사중인 문자열 => node : 큐의 맨 앞에 있는 문자열
string node = q.front();
q.pop();
//현재 검사중인 문자열이 찾을 문자열이면 index(단계)를 반환
if (node == target)
return index;
for (int j = 0; j < words.size(); j++) {
//방문하지 않았고, 다음 문자열로 변환이 가능하다면
if (!visited[j] && changeable(node, words[j])) {
//큐에 추가해주고 방문 처리
q.push(words[j]);
visited[j] = true;
}
}
}
index++; // 큐의 한 요소에 대한 탐색( 한 단계)가 끝나고 인덱스 증가
}
return 0; //타겟에 도달하지 못하면 0 반환
}DFS로 풀이
#include <string>
#include <vector>
using namespace std;
vector<bool> visited(51,false);
bool changeable(string before, string after) {
int diff = 0;
for(int i = 0; i < before.size(); i++) {
if(before[i] != after[i])
diff++;
}
return diff == 1;
}
// DFS 함수
int DFS(const string& current, const string& target, vector<string>& words, int depth) {
//타겟 단어를 찾으면 단계(타겟을 찾으러 내려간 깊이) 반환
if (current == target)
return depth;
int minDepth = 0; // 최소 깊이 초기화(루트)
for (int i = 0; i < words.size(); i++) {
//아직 방문하지 않았고 현재 단어에서 변환 가능한 단어이면
if (!visited[i] && changeable(current, words[i]))
{
//방문 처리
visited[i] = true;
//해당 노드를 기준으로 다음 노드 방문을 위해 DFS 재귀
//단계 증가
int result = DFS(words[i], target, words, depth + 1);
//최소 깊이 갱신해주기!(루트에서 다음 자식이동...등)
if (result != 0)
{
if (minDepth == 0 || result < minDepth)
minDepth = result;
}
//이 길이 더이상 답이 없으면 방문처리 취소( 백트래킹)
visited[i] = false; // 백트래킹
}
}
return minDepth;
}
int solution(string begin, string target, vector<string> words) {
int answer = DFS(begin, target, words, 0);
return answer;
}