글 읽기 - 혹시 틀린점 좀 알려주실 수 있으신가요..

tjdvyzl12 2년 전 0

일단 문제에 나와있는 그림을 예시로 보고 1에서 dfs를 시작해서 3 4 를 탐색 한 후, 3에서 다시 dfs를 시작할 때 1 4 를 중복 탐색하는 것을 방지하기 위해서 1에서 dfs를 했을 때 방문처리를 통해 이 때 방문한 1의 개수만큼 산책할 수 있는 경로 개수에 곱해서 total_cnt에 추가하는 식으로 구현해봤습니다. 어떤 점이 틀렸는지 반례가 없어서 잘 모르겠습니다.. 조언좀 해주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;

#define FIO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int T;
string S;
bool check[200001]; // 중복 방지
int total_cnt = 0;

int one = 1; // dfs로 탐색하는 과정에서 1의 개수
int temp_cnt = 0; // dfs 하는 과정에서 해당 노드에 대해 갈 수 있는 루트의 개수

vector<int> tree[200001];

// 1은 실내(검정)    0은 실외(흰색)

void input() {
	cin >> T;
	cin >> S;
	for (int i = 0; i < T - 1; i++) {
		int par, chi;
		cin >> par >> chi;
		tree[par].push_back(chi);
		tree[chi].push_back(par);
	}
}

void dfs(int input, int bound) {
	check[input] = true;
	if (input != bound && S[input - 1] == '1') {
		temp_cnt++;
		one++;
		return;
	}

	for (int i = 0; i < tree[input].size(); i++) {
		int next_dst = tree[input][i];
		if (check[next_dst] != true)
		{
			dfs(next_dst, bound);
		}
	}
}

int main() {
	FIO;

	input();

	for (int i = 1; i <= T; i++) {
		if (S[i - 1] == '1') {
			check[i] = false;
			dfs(i, i);
			total_cnt += temp_cnt * one;
			temp_cnt = 0;
			one = 1;
		}
	}

	cout << total_cnt << "\n";
}

rootsquare 2년 전 0

반례 입니다.

10
1011101111
1 2
4 2
3 2
2 5
5 10
6 10
6 7
6 8
6 9

올바른 출력: 26

이 코드의 출력: 20

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

문제

문제

출처

ICPC

혹시 틀린점 좀 알려주실 수 있으신가요..

tjdvyzl12 2년 전 0

rootsquare 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말