글 읽기 - 어떤 부분에서 틀린생각인지 알고싶습니다.

hzw94 4년 전 0

제가 생각한 로직은 일단 탐색을하는데

탐색 하면서 자식노드 = 부모노드 + 1 임을 통해서

탐색이후에 주어진 제시 수열에서 자식노드들이 부모노드들보다 일찍나오면 틀리다는점을 이용해서 문제를 해결하려했는데

계속 50%정도에서 걸리네요.

제가 궁금한건

첫째, 이러한 로직 자체가 틀린것일지

둘째, 만약 이 로직으로 풀수있다면 추가해야될게 무엇인지

혹시 아시는분이 있으시다면 답변주시면 정말 감사하겠습니다 ㅠㅠ

#include<iostream>
#include<queue>
#include<vector>
#include<utility>

using namespace std;

int n;
vector<int> v[100001];
int d[100001];
bool dist[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		
		v[x].push_back(y);
		v[y].push_back(x);
	}
	vector<int> right;
	for (int i = 0; i < n; i++) {
		int al;
		cin >> al;
		right.push_back(al);
	}
	if (v[1].size() == 0) {
		cout << 0 << '\n';
		return 0;
	}
	queue<int>q;
	q.push(1);
	dist[1] = true;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			if (dist[v[x][i]] == false) {
				dist[v[x][i]] = true;
				d[v[x][i]] = d[x] + 1;
				q.push(v[x][i]);
			}
		}
	}
	bool go = false;
	for (int i = 1; i < n; i++) {
		if (d[right[i-1]] > d[right[i]])
		{
			cout << 0 << '\n';
			go = true;
			break;
		}
	}
	if (go == false) {
		cout << 1 << '\n';
	}return 0;
	
}

hzw94 4년 전 0

아 이런, 부모노드의 정보도 포함이되야하네요;;

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 부분에서 틀린생각인지 알고싶습니다.

hzw94 4년 전 0

hzw94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말