프로그래머스 - dfs/bfs(타겟 넘버, 네트워크, 단어 변환, 여행경로)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12421

👀문제이해 및 풀이방법

오늘은 dfs/bfs 문제들을 풀었다 최근에도 그렇고 정말 많이 풀었던 유형들이라 금방 잘 풀린것 같다.
문제들은 재미있었는데 마지막 4번 여행경로가 조금 난해했다 문제 이해도 그렇고 이해 했더라도 백트래킹을 쓰고싶었는데 구현이 생각많큼 쉽지 않았다 결국 visit배열을 포기하고 set으로 지금까지 지나온 곳을 표현하면서 dfs를 돌렸다
조금 난해하긴 해서 다른 코드를 공부해볼 예정이다.
1 2 3 번문제는 문제가 기억이 잘 나지 않을정도로 금방 풀린것 같다

📝코드

1 타겟 넘버

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class problem1{
private:
    vector<int> numbers;
    int target,sol=0;
public:
    problem1(vector<int>& n,int t):numbers(n),target(t){

    }
    void dfs(int cur,int p){
        if(p==numbers.size()){
            if(cur==target)
                sol++;
            return ;
        }
        dfs(cur+numbers[p],p+1);
        dfs(cur-numbers[p],p+1);
    }
    int find_sol(){
        dfs(0,0);
        return sol;
    }
};
int solution(vector<int> numbers, int target) {
    problem1 p1(numbers,target);

    return p1.find_sol();
}

2 네트워크

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
class bfs_basic{
private:
    vector<vector<int>> computers;
    int N;
    vector<bool> visit;
public:
    bfs_basic(int n,vector<vector<int>>& c):N(n),computers(c){
        visit.resize(N,false);
    }
    void bfs(int start){
        queue<int> q;
        q.push(start);
        visit[start]=true;
        int cur;
        while(!q.empty()){
            cur = q.front();
            q.pop();
            for(int i=0;i<computers[cur].size();i++){
                if(computers[cur][i] && !visit[i]){
                    visit[i]=true;
                    q.push(i);
                }
            }
        }
    }
    int find_sol(){
        int sol=0;
        for(int i=0;i<N;i++){
            if(!visit[i]){
                bfs(i);
                sol++;
            }
        }
        return sol;
    }   
};
int solution(int n, vector<vector<int>> computers) {
    bfs_basic bb(n,computers);
    return bb.find_sol();
}

3 단어 변환

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct _node{
    string str;
    int degree;
};
int solution(string begin, string target, vector<string> words) {
    queue<_node> q;
    q.push({begin,0});
    vector<bool> visit(words.size());
    _node cur;
    int cnt;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(cur.str == target)
            return cur.degree;
        for(int i=0;i<words.size();i++){
            cnt=0;
            for(int j=0;j<words[i].size();j++)
                if(words[i][j]!=cur.str[j])
                    cnt++;
            if(cnt ==1 && !visit[i]){
                visit[i]=true;
                q.push({words[i],cur.degree+1});
            }
        }
    }
    return 0;
}

4 여행경로

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_set>
using namespace std;
bool compare(vector<string>& a, vector<string>& b){
    return a[1]>b[1];  
};
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer(tickets.size()+1);
    sort(tickets.begin(),tickets.end(),compare);
    stack<pair<string,unordered_set<int>>> st;
    st.push({"ICN",{}});
    pair<string,unordered_set<int>> cur;
    while(!st.empty()){
        cur = st.top();
        st.pop();
        answer[cur.second.size()]=cur.first;
        if(cur.second.size()==tickets.size())
            return answer;
        for(int i=0;i<tickets.size();i++){
            if(tickets[i][0]==cur.first && cur.second.find(i)==cur.second.end()){
                unordered_set<int> tmp = cur.second;
                tmp.insert(i);
                st.push({tickets[i][1],tmp});
            }
        }
    }
}