프로그래머스 고득점 Kit 하루만에 뽀개기 - 8. 깊이/너비 우선검색(DFS,BFS) C++ 풀이

https://programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

- java풀이와 C++풀이가 거의 차이점이 없어서 C++ 풀이로만 정리하였다

 

1. 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

- numbers에 대해서 재귀적으로 순회하면서 모든 값들을 사용 후에 타겟넘버가 완성되었는지 체크하면 된다.  주어진 숫자의 갯수가 최대 20개이므로 방법의 수는 2^20 = 100만이므로 DFS 완전탐색이 가능하다

#include <vector>
using namespace std;
    
int ans = 0;

void go(int res, int idx, vector<int>& numbers, int target) {
    if(idx == numbers.size()) {
        if(res == target) ++ans;
        return;
    }
    
    go(res + numbers[idx], idx+1, numbers, target);
    go(res - numbers[idx], idx+1, numbers, target);
}

int solution(vector<int> numbers, int target) {
    go(0, 0, numbers, target);
    return ans;
}

 

2. 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

- 컴퓨터간 연결정보가 인접행렬 방식으로 정의되어 있다. 이 경우 모든 노드들을 돌면서 해당 노드에서 연결되지 않은 모든 노드를 dfs탐색 해가면서 탐색이 종료된 후 갯수를 카운트하는 방법 혹은 상호배타적 집합 disjoint-set인지 확인하는 유니온 파인드 알고리즘을 사용해볼 수도 있겠다.

#include <vector>
using namespace std;

bool check[201];

void dfs(int now, vector<vector<int>>& computers) {
    check[now] = true;
    for(int i = 0; i < computers.size(); ++i) {
        if(computers[now][i] && !check[i]) {
            dfs(i, computers);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        if(check[i]) continue;
        dfs(i, computers);
        ++ans;
    }
    
    return ans;
}

 

3. 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

- 규칙에 따라 시작단어로부터 char 1개만 바꿔서 words의 단어 중 하나로 변환(이동) 해나가면서 target에 도달하는 최단과정(최단거리)를 구해야한다. 이 과정을 그래프로 치환하면 이동거리가 1인 그래프 시작점에서 words를 거쳐 target에 도달해야하므로 bfs 탐색을 통해서 최단거리를 구할 수 있다.

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

bool check[51];

bool diff1(string& s1, string& s2) {
    int cnt = 0;
    for(int i = 0; i < s1.length(); ++i) {
        if(s1[i] != s2[i]) ++cnt;
        if(cnt > 1) break;
    }
    return cnt == 1;
}

int solution(string begin, string target, vector<string> words) {
    int N = words.size();
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while(!q.empty()) {
        auto& [fi, se] = q.front();
        q.pop();
        
        if(fi == target) return se;
        
        for(int i = 0; i < N; ++i) {
            if(check[i]) continue;
            if(diff1(fi, words[i])) {
                check[i] = true;
                q.push({words[i], se + 1});
            }
        }
    }
    
    return 0;
}

 

4. 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

- "ICN"에서 출발하여 모든 tickets를 이용할 수 있는, 사전순으로 제일 빠른 경로를 구해야한다.
티켓 순서를 사전순으로 정렬 한 뒤 ICN으로 시작하는 티켓으로 시작하는 dfs 탐색을 시작한다. 종료조건으로 모든 티켓을 사용하는 경우로 설정하고 모든 장소들을 다 넣어보면서 시작지점으로부터 도달 가능한데 방문하지 않은 공항인 경우 계속 탐색해나간다. 시작지점으로부터 모든 공항에 도달 할 수 없으면 백트래킹 방식으로 탐색루트를 되돌아가야한다. (ans.pop_back())

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool check[10001];
vector<string> ans;

bool go(string u, int len, vector<vector<string>>& tickets) {
    int N = tickets.size();
    ans.push_back(u);
    if(len == N) return true;
    
    for(int i = 0; i < N; ++i) {
        if(tickets[i][0] == u && !check[i]) {
            check[i] = true;
            if(go(tickets[i][1], len+1, tickets)) return true;
            check[i] = false;
        }
    }
    ans.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    go("ICN", 0, tickets);
    return ans;
}