글 읽기 - 시간 초과가 나요ㅠㅠ 고수분들 도와주세요

cksdnwh 6년 전 0

BFS를 이용해서 최댓값을 노가다로 구했습니다.

처음에 이렇게 시도하면 안되겠구나 했는데, 이런 방법으로 성공하신 분들이 계시다고 하셔서 시도 해봤지만 실패..(시간초과)

코드를 지적해 주시던, 아니면 새로운 방법을 설명해 주시면 감사하겠습니다 ㅠㅠ초보좀 살려주세요

#include<stdio.h>

typedef struct node {
	int data;
	struct node* next;
}Node;

typedef Node* NodePtr;

NodePtr First, Rear; //연결리스트의 머리와 꼬리
int N, M;
int net[100000][2]; //간선 입력
int visit[10001] = { 0, }; //한번 방문한 곳은 다시 방문하지 않게 하기위해..

void resetNode(); //처음에 머리와 꼬리를 연결한다
void push(int a); //숫자를 받아 새로운 노드에 삽입한다.
int pop(); //맨 앞의 노드를 없앤다.(First 바로 뒤의 노드)

int main(void)
{	
	resetNode();
	int Answer[10001][2];
	int i, j;
	int max;
	int count;
	scanf("%d %d", &N, &M);

	for (i = 0; i < M; i++) {
		scanf("%d %d", &net[i][0], &net[i][1]); //입력
	}

	max = 0;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			visit[j] = 0;
		}                   //j를 사용한 반복문->visit을 초기화
		push(i);
		visit[i]++;   //순서대로 수를 넣는다.(i 입력)
		Answer[i][0] = i; //수 저장
		Answer[i][1] = Hacking();  //수에 해당하는 값 저장

		if (max < Answer[i][1])  //그중에서 가장 큰 값 저장
			max = Answer[i][1];
	}
	for (i = 1; i <= N; i++) {
		if (Answer[i][1] == max)  //가장 큰 값을  가지고 있는 수 출력
			printf("%d ", Answer[i][0]);
	}
}

int Hacking()  //BFS방식을 사용했다.
{
	int a, i, count = 0;
	while (First->next != Rear) {
		a = First->next->data; //연결리스트 머리 바로 다음 값을 저장

		for (i = 0; i < M; i++) {
			if (a == net[i][1] && !visit[net[i][0]]) { //a와 net에 할당된 수 비교
				visit[net[i][0]]++;
				push(net[i][0]);
			}
		}
		pop();
	}
	for (i = 1; i <= N; i++) { //visit에 표시된 1들의 개수가 곧 우리가 원하는 값
		if (visit[i] == 1)
			count++;
	}
	return count++;  //값 출력
}

void resetNode()
{
	First = (NodePtr)malloc(sizeof(Node));
	Rear = (NodePtr)malloc(sizeof(Node));
	First->next = Rear;
	Rear->next = First;
}

void push(int a)
{
	NodePtr newnode = (NodePtr)malloc(sizeof(Node));
	newnode->data = a;

	if (First->next == Rear)
	{
		First->next = newnode;
		newnode->next = Rear;
		Rear->next = newnode;
	}
	else {
		Rear->next->next = newnode;
		newnode->next = Rear;
		Rear->next = newnode;
	}
}

int pop()
{
	int n;
	NodePtr deleteNode;
	deleteNode = First->next;
	n = deleteNode->data;
	First->next = deleteNode->next;

	if (First->next == Rear)
		Rear->next = First;

	free(deleteNode);

	return n;
}

redball_var 6년 전 1

각 노드에서 bfs 돌려서 감염된 컴퓨터 수를 세는 방법으로 하신 것 같은데. 방법은 좋은 것같습니다.

코드가 복잡해서 오류를 직접 못 찾아드리지만,

제 생각에는 큐를 직접 구현하지 말고 stl 라이브러리 쓰시는게 좋을 것같아요.

저도 처음에는 직접 구현했는데, stl 써보니까 진짜 편하고 빠르게 구현할 수 있더군요.

cksdnwh 6년 전 0

넵 한 번 해보겠습니다

donghwashin 6년 전 1

신뢰하는 관계 M개를 net이라는 배열에 저장하셨고,

BFS 돌릴 때, 노드와 인접한 다른 노드를 찾기 위해서 M번씩 돌리시는 것 때문에 시간초과가 나는 것 같아요.

이럴 경우, BFS로 순회하는 노드 개수 X M (최대 100,000) 번 돌아가게 되는데요.

제 경우는 첨에 이 문제가 인접행렬을 쓰면 (A[10000][10000]) 메모리가 초과되어서

인접리스트를 써야겠다고 생각했고, STL 벡터 안쓰고 인접리스트 직접 만들려고

Node 클래스 정의해서 링크드리스트 기반으로 만들었는데, 그래도 시간초과...

그래서 그냥 벡터를 흉내낸 Dynamic Array를 직접 짠 다음, 그걸 기반으로 인접리스트를 만들어보자..

해서 시간초과 안나고 통과했습니다.

일단 M개의 신뢰하는 관계는 맨 처음 입력을 받을 때에, 한 번만 for문 돌면서

인접리스트 만들 때에만 써주시면 될 것 같구, 그 다음엔 인접리스트를 다뤄서 BFS 돌려보시는게 좋을 것 같아요.

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

문제

문제

출처

ICPC

시간 초과가 나요ㅠㅠ 고수분들 도와주세요

cksdnwh 6년 전 0

redball_var 6년 전 1

cksdnwh 6년 전 0

donghwashin 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말