글 읽기 - 어떤 방식으로 접근해야할지 모르겠습니다.

gydbslove 5년 전 0

dfs 문제여서 dfs 를 구현해보기도 하고 다른 방식으로 접근해보기도 했는데 왜 틀리는지 알 수가 없어서

질문 올립니다. 아래는 코드인데 가장 최근에 생각해서 풀어본 코드입니다. 물론 예제 올바르게 실행되고 컴파일도

잘됩니다. 도와주세요 ㅜㅜ

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
stack <int> s;
vector <pair<int, int>> v[100001];
vector <int> e;
bool check[100001]; 
int cnt[100001]; // 자식의 수
int n;
int now;
bool IsChild(int x) {
	for (int i = 0; i < v[x].size(); i++) {
		int a = v[x][i].second;
		int b = v[x][i].first;
		if (a) { // a 가 1이면 b 는 부모노드
			if (check[b]) { // 부모노드 한번이라도 나왔다면
				cnt[b]--;//읽은 부모노드 자식 감소
				return true;
			}
			else return false;
		}
	}
}
bool IsParent(int x) {
	for (int i = 0; i < v[x].size(); i++) {
		int a = v[x][i].second;
		int b = v[x][i].first;
		if (a) { 
			if (b == now) return true;// 부모노드가 전 노드일 경우
            // 이때는 dfs가 진행중임
			else {
				if (!cnt[now])return true;
                // 또는 전 노드의 자식노드가 없다면 전 노드의 dfs가 완료되었기 때문에
                // 새로운 노드가 온다고 해도 이상이없음
				else {
					return false;
				}
			}
		}
	}
}
int stackManager(int x){
	if (!IsChild(x))return -1;
	if (!IsParent(x))return -1;
    // IsChilde 부모 노드가 한번이라도 나왔다면
    // 부모가 한번도 나오지 않았는데 나타났다면 너무 뜬금포기 때문
    // IsParent 현재 노드의 부모가 전 노드거나 전 노드의 자식이 없을경우를 파악
    // 이 부분은 부모 노드가 한번이라도 나왔더라도 전(before) 노드가 dfs 를 완료했을 경우가
    // 아닌 경우인지 파악
	else now = x;
	s.push(x);
    check[x] = 1;
	while (!cnt[x]){ // 자식이 없다면
		s.pop();  // 빼주고
		if (s.empty()) {
			return 1;
		}
		x = s.top();
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back({ b,0 });
		v[b].push_back({ a,1 }); // 부모노드를 넣어줌
		cnt[a]++; // 자식 노드의 개수
	}
	check[1] = true;	 // 맨 처음 루트노드를 넣어줌
	s.push(1);
	now = 1; 
	int tr = 0, num = 0;
	for (int i = 0; i < n; i++) {
		int r; cin >> r;
		if (r == 1) continue;
		e.push_back(r);
	}
	for (int i = 0; i < n - 1; i++) {
		if ((num = stackManager(e[i])) == 1) {
			cout << 1 << "\n";
			break;
		}
		else if (num == -1) {
			cout << 0 << "\n";
			break;
		}
	}
}

luniro 5년 전 0

출력:
1

정답:
0

저도 이것때문에 삽질했어요

gydbslove 5년 전 0

ㅜㅜ 수정했는데도 안되네요 ㅜㅜ 코드 부분에서 오류인걸까요?

luniro 5년 전 0

처음 시작이 1이 아니면 0을 출력하면 됩니다

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

문제

문제

출처

ICPC

어떤 방식으로 접근해야할지 모르겠습니다.

gydbslove 5년 전 0

luniro 5년 전 0

gydbslove 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말