map 계열 알아야 할점

https://velog.io/@kwt0124/map-%EA%B3%84%EC%97%B4-%EC%9E%98-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0
인데, 나는 key값과 비교하려고 했지만, 디폴트 만들어지니까 set으로 접근했지만, 굳이 그럴 필요는 없었다. 왜냐하면 value값이 true 일때 종료하는 것이므로 생성이 되더라도 문제가 없다.
true는 우리가 설정하는 것이므로

아예 불변수 초기화 부터 하고 시작하는 편이 속 편하다.

풀이전략

• 최소거리를 구하는 것이므로 bfs로 접근하는 것이 빠르다.

• 어떻게 bfs로 접근할지에 대해 고민해봐야 하는 문제다.

  가. hot - dot - dog- log - cog
  나. hot - dot - dog - cog
  다. hot - lot - log - cog
  이런방식으로 접근하는 방법에 따라서 나열할 수 있는데

• 입력값
  begin target words return
  "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4
  "hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0

중간의 값들을 포함 안포함에 대한 처리를 해야하는데,
check 변수를 여기서 사용하면 된다.
그리고 최소값이므로 최소값에 대한 저장을하는 변수가 필요하다.
예를 들면 위에서 가.에서는 cog까지 도달하는데 5번이 걸리고
나.에서 cog까지 도달하는데 4번이 걸린다.

만약에 dog에서 탐색을 하면 가.와 나.가 될수 있는데,
과정을 살펴보면 dog -> log [4] // dog -> cog[4] 가 나온다.
순차적으로 하면 가.에서 dog -> log -> cog[5]에 도달하기 전에
나.처럼 dog -> cog[4]에 먼저 도달한다. 그리고 최소값이므로
가.의 cog에 도달하는 것을 기다릴 필요없이 나.과정을 통해
탐색을 끝낼 수가 있다는 것이다...

생각 많이 해야 하는 부분

: 위에서 체크를 했다고 생각하더라도, for문에서 한번더 체크해야 한다.
for문에서 체크하는 부분은 컨테이너를 이용해 확인하는 것이다. 윗부분이랑 다르다.

bfs로 푼 소스코드

#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

bool compare(string a, string b)
{
    int cnt = 0;
    
    for(int i = 0; i < a.length(); i++)
    {
        if(a[i] != b[i])
            cnt++;
        if(cnt > 1)
            return false;
    }
    
    if(cnt != 1)
        return false;
    
    return true;
}


int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    queue<pair<string, int>>q;
    unordered_map<string, bool> check;
    
    for(const string &i : words)
    {
        check[i] = false;
    }
    
    int cnt = 0;
    q.push({begin, cnt});
    
    
    while(!q.empty())
    {
        //기준값.
        string word = q.front().first;
        int num = q.front().second;
               
        q.pop();
        
        if(word == target)
        {
            return num;
        }
        
        if(check[word] == true)
            continue;
        check[word] = true;
        
        for(int i = 0; i < words.size(); i++)
        {
            if(compare(word, words[i]) && check[words[i]] == false)
            {
                q.push({words[i], num + 1});
            }
        }

    }
    
    
    
    
    return answer;
}