글 읽기 - 구슬찾기 문제 3일째 입니다...

skfnxh0124 6년 전 0

dfs구현 했습니다 . 각 정점에서 몇개까지 큰것이 있는지 작은 것이 있는지 조사한 후에 문제를 풀이하는 식으로 했습니다.

문제조건에서 " 무게가 모두 다른 N개의 구슬이 있다."라고 하였으니 싸이클은 생각하지 않았습니다만.

8%에서 계속 틀렸습니다가 나옵니다... dfs구현 시 check함수 초기화하면서 안했던 점을 고쳤음에도 불구하고 똑같습니다..

도와주세요!

#include <iostream>
using namespace std;
int circle[101][2]; //나보다 가벼운 것 무거운 것 갯수  [0] - 무거운것 [1] - 가벼운 것
int map[101][101]; //입력 값
bool check[101][101]; //췤
int ans[101]; //될수 없는 것들 체크하기.
int N;
void init()
{
	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			map[i][j] = 0;
			check[i][j] = 0;
		}
		ans[i] = 0;
		for (int j = 0; j < 2; j++)
			circle[i][j] = 0;
	}

}
void check_init()
{
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
			check[i][j] = 0;
}
int to_circle_bigger(int n);
int to_circle_smaller(int n);
int main()
{


	int test_case;
	cin >> N >> test_case;

	init();
	while (test_case)
	{
		int x, y;//x>y
		cin >> x >> y;
		map[x][y] = 1;
		test_case--;
	}


	//무거운 것 넣기
	for (int i = 1; i <= N; i++)
	{
		check_init();
		circle[i][0]=to_circle_bigger(i);
	}

	// 가벼운 것 넣기
	for (int i = 1; i <= N; i++)
	{
		check_init();
		circle[i][1]=to_circle_smaller(i);
	}
	int mid = (N + 1) / 2;

	for (int i = 1; i <= N; i++)
	{
		if (circle[i][0] >= mid)
			ans[i] = 1;
		if (circle[i][1] >= mid)
			ans[i] = 1;
	}
	
	
	int count = 0;
	for (int i = 1; i <= N; i++)
		if (ans[i] == 1)
			count++;
	cout << count << endl;
	return 0;
}
int to_circle_bigger(int n)
{
	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
		if (map[i][n] == 1) //i>n 입니당. n의 무거운 거 갯수를 올려주세용.
		{

			if (check[i][n] == 0)
			{
				cnt++;
				cnt += to_circle_bigger(i);
				check[i][n] = 1;
			}

		}
		
	}
	return cnt;
}
	int to_circle_smaller(int n)
	{
		int cnt = 0;
		for (int i = 1; i <= N; i++)
		{
			if (map[n][i] == 1) //n>i 입니당. n의 가벼운 것 갯수를 올려주세용.
			{

				if (check[n][i] == 0)
				{
					cnt++;
					cnt += to_circle_smaller(i);
					check[n][i] = 1;

				}

			}
			
		}
		return cnt;
	}

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

문제

문제

출처

ICPC

구슬찾기 문제 3일째 입니다...

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말