글 읽기 - 반레좀 찾아주세요ㅠ

check_mate 6년 전 0

질문에 올라와있는 답변들에 있는 반례들이랑 예제는 잘돌아가는데 1%도 안올라가고 틀렸다고 뜹니다...ㅜㅜㅜ

#include <stdio.h>
#define max 101
int map[max][2] = { 0, }; //[0]과 [1]은 연결 
int Queue[max][2] = { 0, }; // [0]:시작,[1]:끝
int Check[max] = { 0,1, };
int main(void) {
	int Com_Num; //컴퓨터 수
	int Net; //네트워크 연결 수
	int Bi; //바이러스가 걸린 컴퓨터 수
	scanf("%d", &Com_Num);
	scanf("%d", &Net);
	for (int i = 0; i < Net; i++) {
		scanf("%d %d", &map[i][0], &map[i][1]);
	}
	int EnQueue_index = 0;
	int DeQueue_index = 0;
	
	Queue[EnQueue_index][0] = 0;
	Queue[EnQueue_index][1] = 1;
	Bi = 0;
	EnQueue_index++;
 	while (EnQueue_index != DeQueue_index) {
		int B = Queue[DeQueue_index][1];
		DeQueue_index++;
		for (int i = 0; i < Com_Num; i++) {
			if (B == map[i][0]&&Check[map[i][1]]==0) {
				Queue[EnQueue_index][0] = map[i][0];
				Queue[EnQueue_index][1] = map[i][1];
				Check[map[i][1]] = 1;
				EnQueue_index++;
				Bi++;
			}
			if (B == map[i][1] && Check[map[i][0]] == 0) {
				Queue[EnQueue_index][0] = map[i][1];
				Queue[EnQueue_index][1] = map[i][0];
				Check[map[i][0]] = 1;
				EnQueue_index++;
				Bi++;
			}
		}
	}
	printf("%d", Bi);
	
	
	return 0;
}

keith 6년 전 0

흠.. 자세히는 훑어보진 않았지만, (그렇다고 너무 성의없다고 뭐라하진 말아주세용. ^^)

가끔 저 마지막 줄에 %d\n (개행문자) 안했을때 오류 뜨던데... 그것때문이 아닐까 의심해 봅니다.^^;

그나저나, Queue 에 2개짜리 int가 들어가는데 [0]은 안쓰이는거 같은데(아무래도 어디서부터 왔는지를 넣어두는거 같은데.. 그럴 의미가?)

check_mate 6년 전 0

\n을 넣어봤지만 틀렸습니다가 바로뜨네요ㅠ

그러고 Queue를 항상 배열2~3칸으로 짜다보니 습관적으로 [0]에 저장한거같네요ㅋㅋㅋㅋ

그래서 충고받은 [0]은 지웠습니다!

#include <stdio.h>
#define max 101
int map[max][2] = { 0, }; //[0]과 [1]은 연결 
int Queue[max] = { 0, }; // [0]:시작,[1]:끝
int Check[max] = { 0,1, };
int main(void) {
	int Com_Num; //컴퓨터 수
	int Net; //네트워크 연결 수
	int Bi; //바이러스가 걸린 컴퓨터 수
	scanf("%d", &Com_Num);
	scanf("%d", &Net);
	for (int i = 0; i < Net; i++) {
		scanf("%d %d", &map[i][0], &map[i][1]);
	}
	int EnQueue_index = 0;
	int DeQueue_index = 0;

	Queue[EnQueue_index] = 1;
	Bi = 0;
	EnQueue_index++;
	while (EnQueue_index != DeQueue_index) {
		int B = Queue[DeQueue_index];
		DeQueue_index++;
		for (int i = 0; i < Com_Num; i++) {
			if (B == map[i][0] && Check[map[i][1]] == 0) {
				Queue[EnQueue_index] = map[i][1];
				Check[map[i][1]] = 1;
				EnQueue_index++;
				Bi++;
			}
			if (B == map[i][1] && Check[map[i][0]] == 0) {
				Queue[EnQueue_index] = map[i][0];
				Check[map[i][0]] = 1;
				EnQueue_index++;
				Bi++;
			}
		}
	}
	printf("%d\n", Bi);


	return 0;
}

keith 6년 전 0

허허, 글쎄요.. 저도 동일한 알고리즘이었는데 문제없이 통과했거든요... (단 다른점은 BFS가 아닌, 재귀를 통한 DFS 였습니다.) 뭔가 한눈에 보이지 않는, 미세한 오류가 있는듯 한데요?

혹시 모르니, Queue 값을 늘려보심이? Queue에 넣기 전에 중복체크를 하므로, EnQueue_index가 100을 넘을 일은 없을것 같아 보이는데,

켁.. 전 도움이 안될듯..

check_mate 6년 전 0

혹시나 해서 이전에 제출을 할때 max의 값을 100000으로 늘려서 해봤는데 그때도 틀렸습니다 가 바로 뜨더군요ㅜ

그래도 봐주셔서 감사합니다!

djm03178 6년 전 1

아래 코드 기준으로 24번째 줄이 잘못되었습니다. 반례는 다음과 같습니다.

1 2

2 3

3 4

4 1

1 3

4 5

정답은 4이지만, 3이 출력됩니다.

check_mate 6년 전 0

반복문이 돌아야 하는게 Com_Num 이 아니라 Net의 수만큼이였네요! 감사합니다!!

#include <stdio.h>
#define max 101
int map[max][2] = { 0, }; //[0]과 [1]은 연결 
int Queue[max] = { 0, }; // [0]:시작,[1]:끝
int Check[max] = { 0,1, };
int main(void) {
	int Com_Num; //컴퓨터 수
	int Net; //네트워크 연결 수
	int Bi; //바이러스가 걸린 컴퓨터 수
	scanf("%d", &Com_Num);
	scanf("%d", &Net);
	for (int i = 0; i < Net; i++) {
		scanf("%d %d", &map[i][0], &map[i][1]);
	}
	int EnQueue_index = 0;
	int DeQueue_index = 0;

	Queue[EnQueue_index] = 1;
	Bi = 0;
	EnQueue_index++;
	while (EnQueue_index != DeQueue_index) {
		int B = Queue[DeQueue_index];
		DeQueue_index++;
		for (int i = 0; i < Net; i++) {
			if (B == map[i][0] && Check[map[i][1]] == 0) {
				Queue[EnQueue_index] = map[i][1];
				Check[map[i][1]] = 1;
				EnQueue_index++;
				Bi++;
			}
			if (B == map[i][1] && Check[map[i][0]] == 0) {
				Queue[EnQueue_index] = map[i][0];
				Check[map[i][0]] = 1;
				EnQueue_index++;
				Bi++;
			}
		}
	}
	printf("%d\n", Bi);


	return 0;
}

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

문제

문제

출처

ICPC

반레좀 찾아주세요ㅠ

check_mate 6년 전 0

keith 6년 전 0

check_mate 6년 전 0

keith 6년 전 0

check_mate 6년 전 0

djm03178 6년 전 1

check_mate 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말