깊이/너비 우선 탐색(DFS/BFS)

네트워크

1차 시도

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    vector <int> networks;
    for (int i=0; i<n; i++) networks.push_back(i);
    
    for (int i=0; i<computers.size(); i++) {
        for (int j=i+1; j<computers.size(); j++) {
            if (computers[i][j]) {
                int base_network = networks[i];
                int replace_network = networks[j];

                for (int k=0; k<networks.size(); k++) {
                    if (networks[k] == replace_network) networks[k] = base_network;
                }
            }
        }
    }
    
    sort(networks.begin(), networks.end());
    auto iter = unique(networks.begin(), networks.end());
    networks.erase(iter, networks.end());
    
    return networks.size();
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.95MB)
  테스트 2 〉	통과 (0.01ms, 3.94MB)
  테스트 3 〉	통과 (0.01ms, 3.96MB)
  테스트 4 〉	통과 (0.02ms, 3.89MB)
  테스트 5 〉	통과 (0.01ms, 3.93MB)
  테스트 6 〉	통과 (0.04ms, 3.89MB)
  테스트 7 〉	통과 (0.01ms, 3.93MB)
  테스트 8 〉	통과 (0.02ms, 3.93MB)
  테스트 9 〉	통과 (0.02ms, 3.89MB)
  테스트 10 〉	통과 (0.02ms, 3.93MB)
  테스트 11 〉	통과 (0.06ms, 4.01MB)
  테스트 12 〉	통과 (0.05ms, 3.88MB)
  테스트 13 〉	통과 (0.03ms, 3.94MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0

단어 변환

1차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int DFS(string begin, string target, vector<string> words, unordered_set<string> checked, int dipth) {
    if (words.size() < dipth) return 0;
    
    checked.insert(begin);
    
    for (int i=0; i<words.size(); i++) {
        if (checked.find(words[i]) != checked.end()) continue;
        
        int canReplace = 0;

        for (int j=0; j<begin.length(); j++) {
            if (begin[j] != words[i][j]) canReplace++;

            if (canReplace > 1) break;
        }
        
        if (canReplace == 1) {
            if (words[i] == target) return dipth;
            
            int s = DFS(words[i], target, words, checked, dipth + 1);
            if (s != 0) return s;
        }
    }

    return 0;
}

int solution(string begin, string target, vector<string> words) {
    return DFS(begin, target, words, {}, 1);
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.94MB)
  테스트 2 〉	통과 (0.01ms, 3.96MB)
  테스트 3 〉	통과 (0.03ms, 3.95MB)
  테스트 4 〉	통과 (0.01ms, 3.95MB)
  테스트 5 〉	통과 (0.01ms, 3.72MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0

테스트 1
  입력값 〉	"hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]
  기댓값 〉	4
  실행 결과 〉	실행한 결괏값 5이(가) 기댓값 4와(과) 다릅니다.
테스트 2
  입력값 〉	"hit", "cog", ["hot", "dot", "dog", "lot", "log"]
  기댓값 〉	0
  실행 결과 〉	테스트를 통과하였습니다.
테스트 3
  입력값 〉	"hit", "cog", ["cog", "log", "lot", "dog", "hot"]
  기댓값 〉	4
  실행 결과 〉	테스트를 통과하였습니다.
테스트 4
  입력값 〉	"1234567000", "1234567899", ["1234567800", "1234567890", "1234567899"]
  기댓값 〉	3
  실행 결과 〉	테스트를 통과하였습니다.
테스트 5
  입력값 〉	"hit", "hot", ["hot", "dot", "dog", "lot", "log"]
  기댓값 〉	1
  실행 결과 〉	테스트를 통과하였습니다.
테스트 6
  입력값 〉	"hot", "dog", ["hot", "dog"]
  기댓값 〉	0
  실행 결과 〉	테스트를 통과하였습니다.

테스트 결과 (~˘▾˘)~
  6개 중 5개 성공

2차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int BFS(string begin, string target, vector<string> words, unordered_set<string> checked, int dipth) {
    if (words.size() < dipth) return 0;

    int min = words.size()+1;

    checked.insert(begin);
    
    for (int i=0; i<words.size(); i++) {
        if (checked.find(words[i]) != checked.end()) continue;
        
        int canReplace = 0;

        for (int j=0; j<begin.length(); j++) {
            if (begin[j] != words[i][j]) canReplace++;

            if (canReplace > 1) break;
        }
        
        if (canReplace == 1) {
            if (words[i] == target) return dipth;

            int value = BFS(words[i], target, words, checked, dipth + 1);
            
            if (value != 0 && min > value) min = value;
        }
    }

    return (min != words.size()+1) ? min : 0;
}

int solution(string begin, string target, vector<string> words) {
    return BFS(begin, target, words, {}, 1);
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.76MB)
  테스트 2 〉	통과 (0.02ms, 3.96MB)
  테스트 3 〉	통과 (0.04ms, 3.72MB)
  테스트 4 〉	통과 (0.01ms, 3.95MB)
  테스트 5 〉	통과 (0.01ms, 3.95MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0