글 읽기 - 구슬찾기 문제입니다 dfs로 풀었는데 코드상에 문제를 찾아주세요 ..

skfnxh0124 6년 전 0

map : 2차원 배열에 (i,j)==1은 i>j를 의미합니다.

check : 말 그대로 탐색을 했는지.

각 구슬마다 자신보다 큰 것의 개수, 작은 것의 개수를 찾을려고 dfs로 구현을 했습니다.

그래서 큰 것이나 작은 것이 (전체구슬+1)/2 보다 크거나 같다면 중앙이 아닐 것이라고 판단했습니다.

제가 몇가지 테스트 케이스 만들어서 했는데도 틀린 것이 없는데 ..어디서틀렸을까요 .

#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 to_circle_bigger(int n);
void 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++)
		to_circle_bigger(i);
	//반대로 하기위한 절차.
	for (int i = 0; i < 101; i++)
		for (int j = 0; j <101; j++)
			check[i][j] = 0;
	// 가벼운 것 넣기
	for (int i = 1; i <= N; i++)
		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;
}
void to_circle_bigger(int n)
{
	for (int i = 1; i <= N; i++)
	{
		if (map[i][n] == 1) //i>n 입니당. n의 무거운 거 갯수를 올려주세용.
		{
			if (check[i][n] == 0)
			{
				check[i][n] = 1;
				circle[n][0]++;
				to_circle_bigger(i);
				circle[n][0] += circle[i][0];
			}
		}
	}
}
void to_circle_smaller(int n)
{
	for (int i = 1; i <= N; i++)
	{
		if (map[n][i] == 1) //n>i 입니당. n의 가벼운 것 갯수를 올려주세용.
		{
			if (check[n][i] == 0)
			{
				circle[n][1]++;
				to_circle_smaller(i);
				check[n][i] = 1;
				circle[n][1] += circle[i][1];
			}

		}
	}
}

chogahui05 6년 전 1

생각해 보니..

추를 기준으로 dfs를 돌릴 때. Tree라는 보장이 없기 때문에 (Tree 같은 경우 노드 갯수 - 1 = 간선 갯수를 만족합니다.)

dfs를 돌리고 난 후에 초기화를 시켜줘야 하는데 그게 아니니

잘못된 값이 나올 수 밖에 없는 거 같네요. 그래프를 구축하는 건 맞습니다.

skfnxh0124 6년 전 0

chogahui05님

답변 남겨주셔서 감사합니다.

그런데 dfs를 돌리고 난 후에 초기화를 한다는 게 어떤 의미인지 모르겠습니다 ㅠㅠ

46~48번 줄이 check함수 초기화 부분인데 다른 곳을 초기화 해야할까요 ???

chogahui05 6년 전 0

dfs를 하실 때 check (혹은 visit) 배열에다가 방문했으면 1을 쓰고, 아니면 0이잖아요.

그걸 초기화 하자는 겁니다.

예를 들어서

1 ---> 3

- ㅅ

- |

-> 2

이런 식으로 연결이 되어 있다고 치면. 1에서는 3개를 갈 수 있겠지만, 2에서는 2개, 3에서는 1개만 갈 수 있지요.

skfnxh0124 6년 전 0

글이 중간에 꺠졌네요 ㅠㅠ.....

슬랙에 다이렉트 메세지로 질문 드렸습니다만

dfs를 할 때 check로 방문했던 것을 확인하는데 방문을 하지 않았다면 그 다음노드로 들어가면서 정보를 circle에 저장합니다.

그 후 방문한다면 circle에 정보를 가져와서 반환하는 식으로 구현을 했습니다.

chogahui05님 께서 말씀해주신거 곱씹어 봐도 어느부분이 틀린지를 잘 모르겠습니다..

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

문제

문제

출처

ICPC

구슬찾기 문제입니다 dfs로 풀었는데 코드상에 문제를 찾아주세요 ..

skfnxh0124 6년 전 0

chogahui05 6년 전 1

skfnxh0124 6년 전 0

chogahui05 6년 전 0

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말