📝 문제 정보#
🧐 관찰 및 접근#
- 풀이1
- 문제 그대로 큐에 넣으면서 시뮬레이션해볼 수 있겠다.
- 같은 레벨 안에서 원하는대로 선택할 수 있으니, 다음으로 들려야하는걸 셋으로 잘 관리하면서 해보자.
- 풀이2
- 현재 내가 있는 노드, 그리고 다음 노드를 큐에 넣을 수 있는지를 체크하는 노드 두가지로 문제를 시뮬레이션하자.
- cidx에서 nidx로 갈 수 있으면 nidx++를 하고, 없을때 cidx를 ++하자.
- nidx가 N에 닿지 못했다면 불가능한 것이다.
- 이 풀이는 트리가 아닌 그래프에서만 가능하다!
💻 풀이#
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<vector<int>> links(N+1);
rep(i, 0, N-1){
int u, v; cin >> u >> v;
links[u].push_back(v);
links[v].push_back(u);
}
vector<int> order(N);
bitset<100001> visited;
rep(i, 0, N) cin >> order[i];
queue<set<int>> v;
v.push({1});
visited[1] = true;
int idx = 0;
while(idx < N){
set<int> nset;
while(!v.empty() && v.front().empty()) v.pop();
if(v.empty()){
cout << 0;
return;
}
if(v.front().count(order[idx]) == 0){
cout << 0;
return;
}
int cur = order[idx];
v.front().erase(cur);
for(int nxt: links[cur]){
if(visited[nxt]) continue;
visited[nxt] = true;
nset.insert(nxt);
}
v.push(nset);
idx++;
}
cout << 1;
}- 풀이2 (Python)
import sys
input = sys.stdin.readline
N = int(input())
links = [set() for _ in range(N + 1)]
for _ in range(N-1):
a, b = map(int, input().split())
links[a].add(b)
links[b].add(a)
lst = list(map(int, input().split()))
if lst[0] != 1:
print(0)
exit()
nidx = 1
cidx = 0
while cidx < N and nidx < N:
if lst[nidx] in links[lst[cidx]]:
nidx += 1
else:
cidx += 1
if nidx == N:
print(1)
else:
print(0)