[프로그래머스 그래프 탐색 DFS/BFS] (level 3) 3번 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163#

코딩테스트 연습 - 단어 변환

---

아이디어 :

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; } Colored by Color Scripter

cs