😫😫😫
#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를 재귀 호출하는지