[C++]단어 변환

요약

• BFS 적용
• 문자열의 문자 비교

  풀이과정

  이 문제는 최소 단계의 과정을 거쳐 변환하는 것을 물어보고 있다. 따라서 BFS가 적합하다. 이를 위해 Queue로 구현할 것이다.

  1. 문자열 비교 함수 만들기

  bool bCanChng(string a, string b)
  {   //문자열 a가 b로 변환이 가능한지 True, False를 반환하는 함수
    int diffCnt = 0;
    int len = a.length();
    for(int i = 0; i < len; i++)
    {
        if(a[i] != b[i])
        {
            diffCnt++;
            if(diffCnt > 1) return false;
        }
    }
    return diffCnt == 0 ? false : true; //아예 같은 경우 배제(begin == begin)
  }

  문자열 a와 b가 하나만 다를 경우 true,
  아예 같거나 두개 이상 다를 경우 false를 반환한다.

  BFS

  answer를 반환하기 위해서는 depth를 알아야 한다.
  이를 위해 큐는 Queue<pair<string,int>> q; 로 선언한다.
  또한 이미 queue에 넣었던 words를 또 넣지 않게끔 하기 위해 vector<int> visited을 words의 개수만큼 0으로 초기화한다.

    int len = words.size();
    vector<int> visited(len,0);
    queue<pair<string,int>> q;
    q.push(make_pair(begin,0));

Queue가 완전히 빌 때 까지 while문을 돌게 한다.
words에 있는 모든 문자에 대해
방문하지 않음 AND 변환 가능? 을 확인한다.

• == target : 답을 찾았으므로 depth+1 해주고 return
• != target : queue에 depth+1 하고 push

로 구성된다.

While문을 빠져나왔다는 의미는 답이 도출되지 않았다와 같다. 따라서 마지막은 return 0으로 마무리한다.

코드

#include <bits/stdc++.h>

using namespace std;

bool bCanChng(string a, string b)
{   //문자열 a가 b로 변환이 가능한지 True, False를 반환하는 함수
    int diffCnt = 0;
    int len = a.length();
    for(int i = 0; i < len; i++)
    {
        if(a[i] != b[i])
        {
            diffCnt++;
            if(diffCnt > 1) return false;
        }
    }
    return diffCnt == 0 ? false : true; //아예 같은 경우 배제(begin == begin)
}

int solution(string begin, string target, vector<string> words) {
    int len = words.size();
    vector<int> visited(len,0);
    queue<pair<string,int>> q;
    q.push(make_pair(begin,0));

    while(!q.empty())
    {
        for(int i = 0; i<len; i++)
        {
            if(!visited[i] && bCanChng(q.front().first,words[i]))
            {
                if(words[i] == target)
                {
                    return ++q.front().second;
                }
                else
                {
                    q.push(make_pair(words[i],++q.front().second));
                    visited[i]++;
                }
            }
        }
        q.pop();
    }
    return 0;
}

기억할 점

딱..히?
depth를 처리할 방법을 빨리 떠올리지 못했다.

다른사람의 풀이

DFS로 푼 사람이 꽤 많아보였다. 그치만 문제 조건 상, BFS가 더 적합하다고 생각이 든다.