Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 삼성SW테스트
- 코딩테스트
- 브루트포스
- dp
- 코딩스킬
- substr
- 백트래킹
- 문자열
- 프로그래머스
- swea
- Sort
- 시뮬레이션
- 삼성SW역량테스트
- 레벨3
- Set
- 이런게4문제
- KAKAO
- 모의SW역량테스트
- Map
- C++
- 완전탐색
- priority_queue
- 백준
- 삼성
- BFS
- find
- STL
- dfs
- 레벨2
- 2018
Archives
- Today
- Total
-
[프로그래머스_레벨 3] 여행 경로 (DFS) 본문
https://programmers.co.kr/learn/courses/30/lessons/43164
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 |
'1-4. 프로그래머스' 카테고리의 다른 글
[프로그래머스_레벨2] 뉴스 클러스터링 (2018 KAKAO BLIND RECRUIT.) (0) | 2020.02.11 |
---|---|
[프로그래머스_레벨 3] 오픈채팅방(2019 KAKAO BLIND RECRUIT.) (0) | 2020.02.11 |
[프로그래머스_레벨 3] 2 x n 타일링 (0) | 2020.02.10 |
[프로그래머스] 레벨 3 - 네트워크 (0) | 2020.02.09 |
[프로그래머스] 레벨 2 - 타겟 넘버 (0) | 2020.02.07 |
Comments