글 읽기 - bfs와 재귀 코드 차이 질문합니다. (스포주의)

hanil0623 2년 전 0

bfs로는 풀었고 이걸 재귀로도 풀고싶은데요

두 코드의 차이가 무엇이길래 4%에서 틀리는지 반례나 이유가 궁금합니다.

감사합니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int ary[328005];
bool flag[328005];
int check[328005];
int n, s, p;
vector<int> v[328005];
queue<pair<int, int>> q;
vector<int> tv;
// 질문 함수, 지지대 블록까지의 거리를 반환하는 함수입니다.
int f(int now, int par) {
	int res = 0;
    // 해당 블록이 지지대 블록이라면 1 반환
	if (flag[now]) return 1;
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (next == par || next == p) continue;
		res += f(next, now);
	}
    // 자식 블록들 중 하나라도 지지대 블록이 있다면 자기 자신의 값을 1 증가
    // 마치 bfs의 depth와 비슷한 역할
	if (res > 0) res++;
	return res;
}
void bfs() {
	// AC 함수입니다.
    // 정답을 위해 생략
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> s >> p;
	for (int i = 1; i <= s; i++) flag[i] = true;
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	check[p] = 1;
	for (int i = 0; i < v[p].size(); i++) {
		int nx = v[p][i];
		//tv.push_back(f(nx, 0));
		q.push({ nx, 1 });
		check[nx] = 1;
	}
	bfs();
    // tv = 펭귄의 위치에서 지지대 블록까지의 depth를 저장함.
	sort(tv.begin(), tv.end());
    // 전체에서 2개 거리 빼고 반환
	cout << n - (tv[0] + tv[1] + 1) << '\n';
	return 0;
}

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

문제

문제

출처

ICPC

bfs와 재귀 코드 차이 질문합니다. (스포주의)

hanil0623 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말