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

🌽 문제

🥔 풀이

먼저 생각해 낸 DFS보다 BFS로 풀어야 더 빠르다고 한다.
왜 이렇게 감을 못 잡는걸까? 배고픈가보다.
레벨3 답게 2레벨보다 훨 오래 고민했다.

DFS랑 BFS는 풀이를 어떻게 적어야할지 모르겠다.
코드를 보는 게 더 빠를 것 같다.

대신 미래의 내가 또 까먹고 또 찾으러 올 만한;
함수 사용법을 정리하는 게 낫겠다.

1-1. string의 find

[사용법]

• str.find(찾을 문자열, 찾기 시작할 위치, 찾을 문자열의 길이)

[반환값]

• 찾으면: 인덱스값
• 없으면: string::npos

#include <algorithm>

string str = "coolgamja";

cout << str.find("gamja"); // 4
cout << str.find("gogooma"); // 18446744073709551615(trash!)

cout << str.find("gamja", 4, 5); // 4
cout << str.find("gamja", 5, 5); // 18446744073709551615(trash!)
cout << (str.find("gamja", 5, 5) == string::npos); // 1(true.)

1-2. algorithm의 find

[사용법]

• find(v.begin(), v.end(), 찾을 값)
• find(arr, arr + arr.size(), 찾을 값)

[반환값]

• 찾으면: vector는 찾을 값의 iterator / array는 포인터
• 없으면: vector는 v.end() / array는 arr.size()

[특징]

• array와 vector에서 사용
• find 반환값에서 범위의 시작값(array/v.begin())을 빼주면
  인덱스값(값을 못 찾은 경우 범위의 크기)을 정확히 얻어낼 수 있다.

#include <algorithm>

vector<string> v = {"hi", "cool", "gamja"};

auto it = find(v.begin(), v.end(), "gamja");
cout << *it; // gamja
cout << it - v.begin(); // 2
    
it = find(v.begin(), v.end(), "gogooma");
cout << (it == v.end()); // 1
cout << it - v.begin(); // 3

#include <algorithm>

int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
// sizeof(arr)는 바이트 단위 배열 크기로, 여기선 4*3으로 12가 된다.

int* p = find(arr, arr + arr.size(), 3);
cout << *p; // 3
cout << p - arr; // 2

p = find(arr, arr + arr.size(), 3);
cout << *p; // (trash)
cout << p - arr; // 3

2. vector의 assign

[사용법]

• v.assign(크기, 초기화 값)

#include <vector>

vector<int> v;

v.assign(100, 1e9);

cstring의 memset으로 1e9 초기화를 했다가 문제가 생겨 알게 된 함수.
참고로 cstring memset은 1바이트 단위로 값을 초기화 하므로,
초기화 값으로 0 또는 char type만 사용할 수 있다.

🥬 코드(DFS)

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<bool> visited;
int answer = 1e9;

bool is1Diff(string a, string b) {
    int diff = 0;
    for (int i = 0; i < a.length(); ++i) {
        if (a[i] != b[i]) diff++;
    }
    return diff == 1;
}

void dfs(string now, string target, vector<string> words, int cnt) {
    if (now == target) {
        answer = min(answer, cnt);
        return;
    }
    
    for (int i = 0; i < words.size(); ++i) {
        if (visited[i]) continue;
        if (is1Diff(now, words[i])) {
            visited[i] = true;
            dfs(words[i], target, words, cnt + 1);
            visited[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int ti = find(words.begin(), words.end(), target) - words.begin();
    int n = words.size();
    if (ti == n) return 0;
    
    visited.assign(n, false);
    
    dfs(begin, target, words, 0);
    
    return answer == 1e9 ? 0 : answer;
}

🥜 채점(DFS)

🥬 코드(BFS)

#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

bool is1Diff(string a, string b) {
    int diff = 0;
    for (int i = 0; i < a.length(); ++i) {
        if (a[i] != b[i]) diff++;
    }
    return diff == 1;
}

int solution(string begin, string target, vector<string> words) {
    int ti = find(words.begin(), words.end(), target) - words.begin();
    int n = words.size();
    if (ti == n) return 0;
    
    vector<bool> visited(n, false);
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while (!q.empty()) {
        auto [now, cnt] = q.front();
        q.pop();
        
        if (now == target) {
            return cnt;
        }
        
        for (int i = 0; i < words.size(); ++i) {
            if (visited[i]) continue;
            if (is1Diff(now, words[i])) {
                q.push({words[i], cnt + 1});
                visited[i] = true;
            }
        }
    }
    
    return 0;
}

🥜 채점(BFS)