프로그래머스 Level 3: 단어 변환[C++]

1. 문제 풀이

 안녕하세요? 문제의 유형은 해쉬 + 너비 우선 탐색이었습니다. 우선 isChange(string, string) 함수를 구현합니다. 두 매개변수가 한 글자만 다르다면 true를 반환하는 함수입니다. 해쉬는 <string, int>로 준비하여 거리 배열처럼 사용하였습니다. begin값을 초기값으로 하여 words의 각 값들과 비교하여 isChange()가 true인 경우, 거리 배열이 갱신될 수 있다면 큐에 삽입하여 진행했습니다. 

 

2. 코드

#include <bits/stdc++.h>

using namespace std;

bool isChange(const string &src, const string &dst) {
    if(src.size() != dst.size()) return false;
    int diff{};
    for(size_t i = 0; i < src.size(); i++) {
        if(src[i] == dst[i]) continue;
        diff++;
    }
    return diff == 1;
}

unordered_map<string, int> d;

int solution(string begin, string target, vector<string> words) {
    d[begin] = 0;
    queue<string> q;
    q.push(begin);
    while(q.size()) {
        auto cur = q.front(); q.pop();
        for(auto &nxt : words) {
            if(!isChange(cur, nxt)) continue;
            if(d.find(nxt) == d.end() || d[nxt] > d[cur] + 1) {
                d[nxt] = d[cur] + 1;
                q.push(nxt);
            }
        }
    }
    
    return (d.find(target) == d.end() ? 0 : d[target]);
}

 

문자열 s에 대해서 작업을 수행하려면 O(|s|)가 걸리는 경우가 조금 있어, 오버헤드로 인한 TLE를 받을까봐 겁이 조금 났습니다. isChange에서 const reference 변수로 둔 이유도 이런 의식이 있어서 그랬습니다. 하지만 기우였습니다. 쉽게 AC를 받을 수 있었습니다.