안녕하세요! 코딩하는 경제학도 쏘코입니다.
DFS/BFS의 마지막 문제입니다. 기존 유형과는 조금 다른 유형이어서 당황했습니다.
푸는데 2일이 걸렸네요 ^^;;;
출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, 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
목차
0. 문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
0.0. 제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
0.1. 입출력 예
| tickets | return |
| [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] | ["ICN", "JFK", "HND", "IAD"] |
| [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] |
0.2. 입출력 예 설명
예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.
1. 풀이 과정
시행착오가 참 많았습니다.
tickets를 정렬하는 것까지는 참 좋았는데, 자동으로 정렬이 되지 않을 것 같아서 cmp를 만들었는데 나중에 알고보니 필요가 없었습니다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그것과는 별개로, 맨 처음 만든 코드는 무조건 알파벳 순서가 앞서는 경로로 진행하면 모든 경로를 다 돌 수 있을 것이라는 헛된 망상으로 만들어낸 코드입니다. 기본 테스트케이스는 모두 잘 돌아가서 기대하면서 돌렸으나 바로 시간초과 오류 발생..
생각해보니 DFS/BFS문제인데 이걸 전혀 사용하지 않았다는 생각이 들었습니다. 경로체크용으로 map을 사용했는데, 막상 잘못된 경로로 이동시에 체크해줄 수 있는 수단이 없더라구요.
그래서 아예 갈아엎고 새로 시작했습니다.
이번에는 DFS를 사용할 것이고, DFS용 함수는 재귀함수로 만들기로 마음먹었습니다.(stack으로도 가능은 한데 조금 더 어려워보입니다.)
가장 먼저 맨 처음 발견한 경로만을 return해야 하기 때문에 전역변수 maxnum = 0을 하나 선언해서, 맨 처음 발견한 완전한 경로만 answer에 저장할 수 있도록 코드를 짰습니다.
solution함수 내부에는 string형태의 vector인 answer, test를 하나씩 만듭니다. test는 경로를 임시저장하기 위한 공간이고, answer는 최종 경로를 저장할 곳입니다.
지나간 경로를 표시하기 위한 bool변수인 chk를 만들었습니다. vector를 초기화하는 방법은 (vector 크기, 값)입니다.
그리고 현재 사용한 티켓의 수를 나타내는 int형 변수인 num을 만들어서 0으로 초기화합니다.
이제 test에 ICN을 넣습니다. 무조건 ICN으로 시작하니까요.
그 다음으로는 tickets를 정렬합니다. 알파벳 순서가 앞서는 경로를 return하기 위해서입니다.
DFS를 돌릴 준비를 끝냈으니 dfs함수를 넣어줍니다.
이제 DFS함수를 만들어줍니다. 파라미터로는 출발지인 start, 주어진 vector인 tickets, 아까 만든 chk, test, answer 벡터들, 그리고 마지막으로 num을 넣어줍니다.
저는 for문을 돌려서 start와 tickets[i][0]이 같은 경우를 찾으려고 합니다. 또한 chk[i]는 false여야겠죠.(쓴 티켓은 또 쓸 수 없으니까!)
만약 그런 티켓을 찾으면 사용했다는 의미로 chk[i]를 true로 바꿔주고, 그 티켓의 도착지를 test에 push_back합니다. 그리고 다시 출발지를 tickets[i][1], num을 num+1로 바꿔주고 dfs를 돌려줍니다.
dfs함수가 더이상 새롭게 dfs함수로 들어가지 않고 끝나게 되면, 다른 경로를 찾기 위해서 chk[i]를 다시 false로 바꿔줍니다. 그리고 test에서 pop_back을 통해 방금 도착한 경로를 제거합니다.
지금까지는 별 다른 체크를 하지 않고 test를 조작했는데, 이제 answer에 저장해 주는 부분을 만들어야 합니다. num(사용한 티켓의 개수)가 maxnum보다 크다면, test에는 지금까지 중에서 가장 많은 경로를 지나쳤다는 이야기가 됩니다. 이 경우에 answer에 test를 복사합니다. (copy함수를 사용하지 않았지만, 얕은 복사가 아닙니다. copy함수를 사용하셔도 동일한 결과를 얻을 수 있습니다.)
추가로 말씀드리면 마지막에 만든 if함수의 위치는 for문 앞과 뒤 어디에 위치해도 상관이 없습니다.
여기까지 만드셨다면 끝입니다! 잘 작동하는 모습을 보실 수 있습니다.
2. 소스 코드
2.0. 시행착오 코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
bool cmp(vector<string>& a, vector<string>& b){ // 앞이 같지 않으면 앞 순서대로, 같으면 뒷 순서대로 정렬
if (a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
map<string, int> m;
string start = "ICN";
answer.push_back(start);
int chknum = 0;
// tickets에서 맨 앞이 ICN인 친구부터 시작하고, 알파벳이 제일 앞쪽인 지역으로 이동
// 먼저 출발지 순서로 정렬, 출발지가 같으면 도착지 순서로 정렬
sort(tickets.begin(), tickets.end(), cmp);
// map에 각 도시별 값을 0으로 넣어줌
for (int i = 0; i < tickets.size(); ++i){
m[tickets[i][0]] = 0;
}
// 도착지 순서대로 정렬했기 때문에, 만약 같은 출발지라면 m[tickets[i][0]]만큼 뒤로 가서 도착지를 찾는다
while(chknum != tickets.size()){
for (int i = 0; i < tickets.size(); ++i){
if(tickets[i][0] == start){
start = tickets[i+m[tickets[i][0]]][1]; // 현재 도착지를 새로운 출발지로 등록
answer.push_back(start); // 현재 도착지를 answer에 넣음
m[tickets[i][0]]++; // 방문횟수를 +1
chknum++; // chknum +1
break;
}
}
}
return answer;
}
2.1. 정답 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
시간 복잡도: O(n)
공간 복잡도: O(n)
사용한 알고리즘: DFS(깊이 우선 탐색)
사용한 자료구조: vector, 재귀
정점이 아닌 경로를 기준으로 DFS를 돌려야 한다
*/
int maxnum = 0; // DFS를 돌릴 때 가장 먼저 발견한 경로만 answer에 남기기 위해
void dfs(string start, vector<vector<string>>& tickets, vector<bool>& chk, vector<string>& test, vector<string>& answer, int num){
if(maxnum < num){
maxnum = num;
answer = test;
}
for (int i = 0; i<tickets.size(); ++i){
if(tickets[i][0] == start && chk[i] == false){
chk[i] = true;
test.push_back(tickets[i][1]);
dfs(tickets[i][1], tickets, chk, test, answer, num+1);
chk[i] = false; // 더 이상 경로가 없어서 dfs가 끝나고 돌아오면 경로 다시 초기화
test.pop_back(); // test에서 도착지 제거
}
}
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
vector<string> test;
vector<bool> chk(tickets.size(),false); // tickets.size()만큼 false로 초기화
test.push_back("ICN"); // 출발지 등록
int num = 0;
// tickets에서 맨 앞이 ICN인 친구부터 시작하고, 알파벳이 제일 앞쪽인 지역으로 이동
// 먼저 출발지 순서로 정렬, 출발지가 같으면 도착지 순서로 정렬
sort(tickets.begin(), tickets.end());
dfs("ICN", tickets, chk, test, answer, num);
return answer;
}
3. 후기
개인적으로 앞에 너무 삽질을 해서 그런지 풀이시간이 상당히 오래 걸렸습니다. (오늘 아침 9시까지는 꼭 풀고싶었지만 결국 풀지 못하고 저녁에서야 풀었다고 합니다..)
DFS/BFS는 분명 빈출문제인데 이렇게 힘을 많이 써서는 곤란한데 ㅠㅠ
독특한 타입의 DFS문제여서 굉장히 재미는 있었습니다.
이제 이분탐색문제로 넘어갑니다! 고득점 KIT도 단 5문제만 남았네요 ㅎㅎ 앞으로의 문제들도 기대됩니다!
최근댓글