https://programmers.co.kr/learn/courses/30/lessons/43163#
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
아이디어 :
1. 노드 가 string인 그래프를 만들어준다. (map을 이용)
ㄴ 1-1 : 부모의 자식은 꼭 부모 문자가 단 하나만 다른놈이여야 한다.
1-2 : 부모가 key 이고 element는 1-1을 만족하는 원소들임
ex)
hit:hot
hot:dot lot
dot:hot dog lot
dog:dot log cog
lot:hot dot log
log:dog lot cog
cog:dog log
2. BFS너비 우선 탐색을 이용하고 처음으로 target 문자열이 나오는 시점의 level을 answer로 한다.
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <iostream>
using namespace std;
bool debug = true;
//그래프를 재구성 해줄 필요가 있어보인다.
//하나만다른것을 찾는것
map<string, vector<string>> G;
map<string, bool> visit;
void PRINT(string _str)
{
cout << _str << ':';
for(string K : G[_str])
cout << K << ' ';
cout << '\n';
}
int isOneCharDiff(string _str1, string _str2)
{
int cnt = 0; int n = _str1.size();
for(int i = 0; i < n; i++)
if(_str1[i] != _str2[i])
cnt++;
return cnt; // 1이 리턴되면 두 단어 비교했을때 다른단어가 1번 나타났다는
}
void makeEdge(string _Begin ,vector<string> _V)
{
//_Begin 노드 그래프 만들기
vector<string> buf;
for(string K : _V)
if(isOneCharDiff(_Begin, K) == 1)
buf.push_back(K);
G.insert(pair<string, vector<string>>(_Begin,buf));
PRINT(_Begin);
//Words 각각간 노드 그래프 만들기
for(string M : _V){
visit.insert({M, false}); buf.clear();
for(string K : _V)
if(isOneCharDiff(M , K) == 1)
buf.push_back(K);
G.insert(pair<string, vector<string>>(M, buf));
PRINT(M);
}
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
if(find(words.begin(), words.end(), target) == words.end()) return 0;
makeEdge(begin ,words);
int level = 0;
queue<pair<string,int>> Q; Q.push({begin, level}); visit[begin] = true;
while(!Q.empty())
{
pair<string,int> curNode = Q.front(); Q.pop();
if(curNode.first == target)
return answer = curNode.second;
for(string K : G[curNode.first]){
if(visit[K] != true)
Q.push({K,curNode.second+1}); visit[K] = true;
}
}
return answer;
}
|
cs |
'PS > 알고리즘' 카테고리의 다른 글
| | 알고리즘 | 3 | 그래프-1 | Stack : DFS | 미로찾기 | (0) | 2022.03.13 |
|---|---|
| [백준 2992] 크면서 작은 수 (다음 순열 찾기 & next_permutation사용법) (0) | 2021.07.09 |
| [백준 1543번] 문서 검색 (c++ <string> 레퍼런스 ) (0) | 2021.07.05 |
| [백준 11719번] 그대로 출력하기 2 (<string> Getline 문자열 공백 허용 입력) (0) | 2021.07.05 |
| [백준 15649번] 백트래킹 N과 M(1) (0) | 2021.07.05 |