글 읽기 - 질문드립니다! 충고부탁드립니다!

tprjs456 2년 전 0

일단 입력받은 결과값이 0으로 시작하면 바로 0을 출력하게 만들었고

BFS탐색을 해서 각 값에 깊이를 level이라는 변수에 저장을 해준 다음 입력받은 결과값에서 자신의 level 보다 높은 level을 갖는 값이 앞에 나와있다면

0 을 출력하게 작성해보았습니다.

예를 들면

4
1 2
1 3
2 4
1 2 4 3

라고 하면 깊이가

1 (깊이 1)

2 3 (깊이 2)

4 (깊이 3)

이렇게 저장 해두고 비교했는데 잘못된 점이 있는지 질문드립니다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>

#define endl "\n"

using namespace std;

bool visited[111111];
int N;
vector<int> vec[111111];
int result[111111];

void Input() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int x, y;
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	for (int i = 0; i < N; i++) { cin >> result[i]; }
	if (result[0] != 1) { cout << 0; exit(0); }
}

int level[111111];
queue<int> q;
int last;
int LEV = 1;

void BFS() {
	q.push(1);
	level[1] = LEV;
	while (q.size() != 0) {
		int x = q.front();
		visited[x] = true;
		q.pop();
		for (int i = 0; i < vec[x].size(); i++) {
			if (visited[vec[x][i]] == false) {
				visited[vec[x][i]] = true;
				q.push(vec[x][i]);
				last = vec[x][i];
				level[vec[x][i]] = level[x] + 1;
			}
		}
	}
	/*for (int i = 1; i <= N; i++) {
		cout << level[i] << " ";
	}cout << endl;*/

	for (int i = 1; i < N; i++) {
		if (level[result[i]] < level[result[i - 1]]) {
			cout << 0;
			return;
		}
	}
	cout << 1; 

}


void Solution() {

	BFS();
}

void Solve() {
	Input();
	Solution();
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();

	return 0;
}

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

문제

문제

출처

ICPC

질문드립니다! 충고부탁드립니다!

tprjs456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말