[문제]
programmers.co.kr/learn/courses/30/lessons/67260
[풀이]
특별한 알고리즘을 사용해서 해결해야되는 문제일줄 알았는데
내가 가장 많이 다루었던 DFS 알고리즘을 사용해 해결하는 문제라는게 놀라웠다.
한번 방문한 곳은 재방문 안해도 된다는 점에 있어서 이해가 안됐는데
모든 경로는 연결되어 있으므로 재방문을 고려하지 않아도 된다.
[코드]
#include <string>
#include <vector>
#include <map>
#define MAX 200000
using namespace std;
vector<int> v[MAX];
int hang[MAX]={0,};
bool visited[MAX]={0,};
map <int,int> post;
void DFS(int idx)
{
if(visited[idx]) return;
if(post.find(idx) != post.end())
{
int pre = post.at(idx);
if(!visited[pre])
{
hang[pre] = idx;
return ;
}
}
visited[idx]=true;
DFS(hang[idx]);
for(int i=0;i<v[idx].size();i++) DFS(v[idx][i]);
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
bool answer = true;
for(auto tmp : path)
{
v[tmp[0]].push_back(tmp[1]);
v[tmp[1]].push_back(tmp[0]);
}
for(auto tmp : order) post.insert(make_pair(tmp[1], tmp[0]));
if(post.find(0) != post.end() ) return false;
visited[0]=true;
for(int idx : v[0]) DFS(idx);
for(int i=0;i<n;i++) if(!visited[i]) answer= false;
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 실패율(C++) (0) | 2021.08.22 |
---|---|
[프로그래머스] 부족한 금액 계산하기(C++) (0) | 2021.08.02 |
[프로그래머스] 호텔 방 배정 (C++) (0) | 2021.04.30 |
[프로그래머스] 징검다리 건너기(C++) (0) | 2021.04.28 |
[프로그래머스] 튜플(C++) (0) | 2021.04.27 |