https://programmers.co.kr/learn/courses/30/lessons/67260
[1.문제 이해]
이 문제는 주어지는 인풋을 바탕으로 트리를 만든다.
이를 바탕으로 '0'지점부터 탐색을 한다.
하지만 선결조건이 있는 트리가 있는데 이에 관해서는 선결조건부터 처리를 해야한다.
[2. 접근방식]
전형적인 트리 탐색문제이다. 이 문제의 경우 노드에서 노드까지의 최소거리를 구하는 문제가 아니므로 단순 완전탐색을 하면된다. 문제는 선결조건에 관해서 어떻게 처리해야지 효율적으로 처리할지를 생각하면 되는문제다. 일반적인 BFS탐색할때 선결조건이 처리가 안된 노드를 만나게 된다면, 이에 관해서 값을 관리하는게 중요했다. 이 문제 해결을 위한 핵심 로직은 다음과 같다.
탐색하다가 선결조건이 있는 노드를 만날 경우..
1. 선결조건 충족O-> 탐색,이때 탐색한 노드에 의해서 선별조건미충족_보류군이 충족돼 탐색가능할 경우 탐색
2. 선결조건 충족X 넘어가기! 선별조건미충족_보류군 컨테이너 에 삽입
[3. 알고리즘 선택]
- 1. 탐색 알고리즘: 트리 탐색에서의 알고리즘의 경우 BFS,DFS어떤것을 써도 상관이 없다. 하지만 코드 작성에 있어서 조금더 직관적 작성이 가능한 BFS로 선택하겠다.
- 2. 선별조건미충족_보류군 컨테이너: 이때 이것을 선택하는게 가장 효율성에 있어 중요한 영향을 끼치는데 자료유형별로 따져보자. 컨테이너의 경우 보류군에 삽입,탐색와 같은 기능을 해야한다.
따라서 해쉬맵을 사용하는 경우가 가장 효율적으로 처리할 수 있다. 물론 동적배열을 사용해 전체 최대 크기만큼 할당을 한후 보류군의경우 true, 나머지의경우 false로 해서 탐색과 삽입을 할 수 도 있다.
[4.전체코드]
#include <bits/stdc++.h>
using namespace std;
#define Vector vector<vector<int>>
#define maxNum 200001
bool Visit[maxNum] = {true};
Vector Path(maxNum);
vector<int> before(maxNum); //선결조건 //
vector<int> after(maxNum); //
queue<int, deque<int>> que;
unordered_map<int, bool> CandidateMap; //true:선결조건 충족하지 못한 next_후보군
int HowManyCount = 0;
bool solution(int n, Vector path, Vector order)
{
for (auto &now : path)
{
Path[now[0]].push_back(now[1]);
Path[now[1]].push_back(now[0]);
}
for (auto &now : order)
{
if (now[1] == 0) return false;
before[now[1]] = now[0]; //0이 해결되야 1을 할 수 있음
after[now[0]] = now[1];
}
que.push(0);
while (!que.empty())
{
while (!que.empty())
{
int from = que.front();
// cout << "now = " << from << "\n";
HowManyCount++;
que.pop();
for (int to : Path[from])
{
if (Visit[to]) //이미 방문했을시
continue;
else //방문해야하고
{
if (Visit[before[to]]) //선결조건 방문했을시
{
que.push(to);
Visit[to] = true;
if(CandidateMap[after[to]]) { //이것을 넣음으로써 선결조건 때문에 못넣은 next_후보군이라면 추가하기
que.push(after[to]);
Visit[after[to]]=true;
CandidateMap[after[to]]=false;
}
}
else CandidateMap[to] = true; //선결집단 넣지못한 next_후보군
}
}
}
}
if (HowManyCount == n) return true;
else return false;
}