글 읽기 - 제발 도와주세요

sinsisao 2년 전 0

bfs로 풀려고했습니다.

예제는 맞게 나오는데 60%에서 계속 틀립니다.

도와주세요. ㅜㅜ

단순히 의견만 제시해 주셔도 큰 도움이 될 것 같습니다. 부탁드려요.

#include <stdio.h>
int N, M, Map[101][101], Ret[101];
int Que[100], F, R;
// n 사람의 베이컨 수를 구하기 위해 만든 bfs 함수 입니다.
void f(int n) {
	int Check[101] = { 0 };
    //체크 배열은 n의 1번부터 N번까지 각각의 사람과의 베이컨 수로 정했습니다.
	F = R = 0;
	Check[n] = -7;                                // 자기 수를 -7로 초기화해서 탐색에서 뺏습니다.
	for (int i = 1; i <= Map[n][0]; i++) {
		Check[0]++;            // 0번 칸을 지금 까지 체크한 수의 갯수로 했습니다.
		Check[Map[n][i]] = 1;  // n과 바로 연결된 숫자들은 관계 수가 1이라 1을 넣었습니다.
		Que[R++] = Map[n][i];
	}

	int p;
    // 큐가 비었거나 모든 사람을 확인한 경우 반복이 끝납니다.
	while (F < R && Check[0] < N - 1) {
		p = Que[F++];
		for (int i = 1; i <= Map[p][0]; i++)
			if (Check[Map[p][i]] == 0) {        // 방문하지 않은 사람일 경우
				Check[0]++;
				Check[Map[p][i]] = Check[p] + 1;
                // 방문합니다. 관계 수는 이사람을 통하기 전 사람 (p) 관계 수에 1을 더한 수로 했습니다.
				Que[R++] = Map[p][i];
			}
	}
    // 모든 연산이 끝나고 Result 배열에 n사람의 총 베이컨수의 합을 계산했습니다.
	for (int i = 1; i <= N; i++)
		Ret[n] += Check[i];
	Ret[n] += 7;
}
// 가장 작은 베이컨 수를 가진 사람을 찾기위해 만든 함수입니다.
int who(void) {
	int min = 0x7fffffff, idx;
	for (int i = 1; i <= N; i++)
		if (min > Ret[i])
			min = Ret[i], idx = i;
	return idx;
}

int main(void) {
	int t1, t2;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d", &t1, &t2);
        //Map배열의 각 행의 0번째에 관계 있는 사람의 수를 저장했습니다.
        //이후 1번부터는 관계있는 사람들이 입력순으로 저장됩니다.
		Map[t1][++Map[t1][0]] = t2;
		Map[t2][++Map[t2][0]] = t1;
	}
    // 1번부터 N번째까지 사람들의 베이컨수를 구합니다.
	for (int i = 1; i <= N; i++)
		f(i);
    // 누가 제일 작은 수를 가졌는지 확인하고 출력합니다.
	printf("%d\n", who());
	return 0;
}

ehddml3 2년 전 0

친구관계가 중복될 수 있다고 했으니 Map[ ][ 이부분 ] 크기가 100보다 클 수 있지 않을까요?

sinsisao 2년 전 0

Map[a][b] 를 a가 Map[a][b]와 관계가 있나 없나로 정의했습니다.

a가 a이 외의 99명과 친구가 될 수 있기 때문에 100개로 했습니다.

친구 관계가 중복된다는건 관계 입력이 동일한 입력이 또 들어 올 수 있다는 건가요?

ehddml3 2년 전 0

입력 부분에 친구 관계는 중복되어 들어올 수도 있으며, 라고 되어있어서용

제가 코드를 이해하기로는 map[a][x] 가 a라는 사람의 친구 x를 들어오는대로 넣어주는거라고 생각해서요.

예를 들면,

1 3

1 4

1 3

이런식으로 입력이 들어오면 map[1][1]=3, map[1][2]=4, map[1][3]=3 이렇게 넣고 계신 것 아닌가요?

sinsisao 2년 전 0

네 맞습니다.

와, 중복이 그 중복이리라고는 생각도 못했는데요..

바로 해봐야겠습니다. 감사합니다.

ehddml3 2년 전 0

음.. 그런데 해보니까 그 부분이 문제는 아니었네용ㄷ 100을 넘게 주지는 않는 것 같네요

그런데 while (F < R && Check[0] < N - 1)

여기에서 문제가 있었네용

while (F < R) 이렇게 바꾸니까 맞네요

아마 11번째 줄에서 중복이 있어도 check[0]값이 ++되어서 다 찾기 전에 끝내버리는 것 같아요

sinsisao 2년 전 1

아, 그러네요 ;;

감사합니다. 덕분에 해결되었습니다.

중복을 주기는 하는군요.. 또다시 문제를 잘 읽어야겠다는 교훈을 얻어갑니다. :)

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

문제

문제

출처

ACM-ICPC

제발 도와주세요

sinsisao 2년 전 0

ehddml3 2년 전 0

sinsisao 2년 전 0

ehddml3 2년 전 0

sinsisao 2년 전 0

ehddml3 2년 전 0

sinsisao 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말