-

[프로그래머스_레벨 3] 여행 경로 (DFS) 본문

1-4. 프로그래머스

[프로그래머스_레벨 3] 여행 경로 (DFS)

asdklfjlasdlfkj 2020. 2. 10. 17:27

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

 

코딩테스트 연습 - 여행경로 | 프로그래머스

[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO]

programmers.co.kr

DFS유형의 문제다.

갈 수 있는 경로를 미리 정렬해서 오름차순의 경로를 반환하면 된다.

현재 경로를 저장하고 계속 가보면서 답을 구하면 된다.

 

void형으로 하지 말고 bool 형으로 해서 했더니 segmentation fault가 나질 않았다.

스택 메모리의 크기에 주의해서 이렇게 bool 형으로 구현하는 방식도 연습이 필요하다.

 

* 22번째줄은 삭제해도 전혀 지장없다.

왜냐하면 타겟 길이만큼 정답을 쌓았을 때 빼고는 모두 false로 리턴해버리기 때문이다. 즉 true인 것이 나오기만 한다면 tickets이 정렬되어 있는 상황에서 처음으로 true 나오면 그것이 가장 앞선 정답이고, 중간에 길이가 짧은 것들은 false로 어차피 리턴되어 버리기 때문에 빼주는 코드를 하지 않아도 짧은 길이의 상태를 제외할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> answer;
bool dfs(string from, vector<vector<string> > tickets, vector<bool> visit, vector<string> curPath){
    curPath.push_back(from);
    if(curPath.size() == tickets.size()+1){
        answer = curPath;
        return true;
    }
    
    for(int i=0; i<tickets.size(); i++){
        if(from == tickets[i][0&& !visit[i]){
            visit[i] = true;
            bool suc = dfs(tickets[i][1], tickets, visit, curPath);
            if(suc)
                return true;
            visit[i] = false;            
        }
    }
   //curPath.pop_back();
    return false;
}
vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());    
    vector<string> curPath;
    vector<bool> visit(tickets.size(), false);
    dfs("ICN", tickets, visit, curPath);
    return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs
 

Comments