글 읽기 - 이게 왜맞나요,,,?

aaaa727 3년 전 0

안녕하세요.

코드 2줄을 지웠습니다.

그 2줄의 코드는

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

문제의 이 부분을 해석하여 7단계로 이어질 경우 갯수를 추가하지 않는 부분입니다.

counting 배열은 bfs 깊이를 저장한 배열입니다.

2줄을 지워버리니 맞았다고 뜹니다. 왜 저부분을 처리해준 코드를 지우니 맞았다고 나오는건가요.?

제가 처리를 잘 못한건가요.?

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int N,M;
vector<int>* vec;
bool v[MAX] = { false, };
int arr[MAX] = { 0, };
//배열에 또 저장
int counting[MAX] = { 0, };
void Input()
{
	cin >> N >> M;
	vec = new vector<int>[N + 1];
	for (int i = 0; i < M; ++i)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
}

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	v[start] = true;
	
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < vec[x].size(); ++i)
		{
			if (v[vec[x][i]] != true)
			{
                /*
                이부분을 추가하니 30%에서 틀렸다고 나옴
                if(counting[x] + 1 > 6)
                    continue;
                */
                
				counting[vec[x][i]] = counting[x] + 1;
				v[vec[x][i]] = true;
				arr[start] += counting[vec[x][i]];
				q.push(vec[x][i]);
			}
		}
	}
}

void Solve()
{
	for (int i = 1; i <= N; ++i)
	{
		memset(v, false, sizeof(v));
		memset(counting, 0, sizeof(counting));
		bfs(i);
	}
	int min = 1000;
	int idx = 1;
	for (int i = 1; i <= N; ++i)
	{
		if (min > arr[i])
		{
			min = arr[i];
			idx = i;
		}
	}
	cout << idx;
}

void solution()
{
	Input();
	Solve();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();
}

aaaa727 3년 전 0

counting[x] + 1 > 7도 아닌

counting[x] + 1 > 8로 하니까 맞았습니다 나오네용.

왜지..

kth 3년 전 0

흠 문제를 다시읽었는데

if(counting[x] + 1 > 6)
continue;

위 코드 부분이 필요없는게 맞네요. 6단계까지라는 입력조건은 존재하지 않네요.

또한 counting[x] + 1 > 8로 바꾸었을 때 성공하는 이유는

한사람으로 부터 최대거리인 count[x]에 대해,

counting[x] > 5 틀림

counting[x] > 6 틀림

counting[x] > 7 맞음

count[x]가 6이나 7인 입력케이스는 존재하고

즉 count[x]가 7을 넘어가는(count[x]가 8인) 입력 케이스가 없다고 생각합니다.

aaaa727 3년 전 0

아하 말은 써 있었지만 직접적으로 조건을 추가하란 말은 없었나 보군요. 감사합니다.

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

문제

문제

출처

ICPC

이게 왜맞나요,,,?

aaaa727 3년 전 0

aaaa727 3년 전 0

kth 3년 전 0

aaaa727 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말