[프로그래머스] 43164 여행경로 C++ - DFS

하스레·2023년 3월 21일
0

문제

프로그래머스 43164_여행경로

난이도

😫😫😫

접근

  • DFS로 풀어야겠다는 생각이 들었다.
    - 이유: DFS는 깊이 우선 탐색으로, 모든 티켓을 다 사용하는 경우는 리프 노드까지 닿는 경우이기 때문이다.
  • 인접리스트를 map으로 구현했다.
    - 이유: string으로 접근할 수 있기 때문이다.
    - 틀린 이유: 티켓이 중복될 수 있는데, map을 사용하면 중복을 제거하여 저장한다.
  • 글로벌 변수로 ans라는 배열을 두었다.
    - 틀린 이유: dfs에 대한 이해가 부족했다. Dfs 함수 내에서 로컬로 사용할 임시 배열을 사용하거나, 파라미터로 path를 넘겨주어야 해당 노드에서 올바른 path를 사용할 수 있다.

내 풀이

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

int num_of_tickets;
unordered_map<string, vector<string>> m;
unordered_map<string, bool> visited;
unordered_map<string, bool> used;

vector<string> ans;
vector<string> real_ans;

vector<string> dfs(int lvl, string cur) {
    
    if(lvl > visited.size()) {
        real_ans = ans;
        return real_ans;
    }
    
    //인접한 노드 보기
    vector<string> adj = m[cur];
    
    for(int i = 0; i< adj.size(); i++) {
        if(visited[cur + adj[i]]) continue;
        
        
        visited[cur + adj[i]] = true;
        ans.push_back(adj[i]);
        
        return dfs(lvl+1, adj[i]);
        //돌아옴
        visited[cur + adj[i]] = false;
        ans.pop_back();
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    num_of_tickets = tickets.size();
    vector<string> answer;
    
    for(int i=0; i<num_of_tickets; i++) {
        m[tickets[i][0]].push_back(tickets[i][1]);
        visited[tickets[i][0] + tickets[i][1]] = false;
    }
    
    for(auto it = m.begin(); it != m.end(); it++) {
        
        sort(it->second.begin(), it->second.end());
    }
    
    ans.push_back("ICN");
    return dfs(1, "ICN");
    
}

정답

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

using namespace std;
bool used[10001];
vector<string> ans;
vector<vector<string>> t;

bool cmp (vector<string> a, vector<string> b) {
    if(a[0] == b[0])
        return a[1] < b[1];
    return a[0] < b[0];
}

void dfs (vector<string> path) {
    if(path.size() > t.size()) {
        //리프에 도달
        if(ans.empty())
            ans = path;
        return;
    }
    
    string cur = path.back();
    for(int i=0; i<t.size(); i++){
        if(used[i]) continue;
        if(cur != t[i][0]) continue;
        
        used[i] = true;
        vector<string> tmp = path; tmp.push_back(t[i][1]);
        
        dfs(tmp);
        used[i] = false;
    }
}

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

소요시간

총 2시간(풀이: 40분 / 정답 해석 및 다시 풀기: 1시간 20분)

배운 점

안 된 이유
1. 첫번째 테케: 똑같은 티켓이 여러장인 경우가 있을 가능성을 간과했다.
-> map 사용하면 안됨!!!
2. dfs로 path를 구하는 경우, path를 글로벌 변수가 아니라 매개변수로 넘겨주자.
-> 글로벌로 하니까 다음과 같이 알파벳 빠른걸 먼저 방문하는게 답이 아닌 경우를 해결할 수 없음!

좋은 아이디어
1. 티켓을 먼저 정렬하고 시작. -> 그러면 알파벳 순으로 방문할 수 밖에 없음

DFS 사용시 중요한 점
1. DFS의 파라미터를 무엇으로 설정할지
2. DFS의 초기값을 뭘로 잡을지
3. DFS 리턴 조건
4. DFS 함수 내에서, 문제에 조건에 맞게 DFS를 재귀 호출하는지


참고
https://96glory.tistory.com/20

profile
Software Developer

0개의 댓글