글 읽기 - 1325 : 메모리 초과 문제를 어떻게 해결해야할까요?...

gksehdgh94 5년 전 0

안녕하세요.. 코알못 유저입니다 ㅜㅜ..

이 문제도 dfs를 이욯하여 풀었는데요.

'A가 B를 신뢰한다'를 2차원배열 map[][]에서 입력을 반대로 주었습니다. => map[v2][v1] 으로

(ex input이 3 1 이면, 1->3이 되게끔)

그리고 dfs를 돌려서 갈 수 있는 모든 정점의 갯수를 cnt로 카운트하고, total배열에 집어넣었습니다.

그리고 total배열의 max값을 구해 max값과 같은 idx를 출력하였습니다.

해결방법이 없을까요? ㅠㅠ

#include <cstdio>
#include <memory.h>

#define MAX_SIZE 10001

using namespace std;

int map[MAX_SIZE][MAX_SIZE];
bool check[MAX_SIZE];

int total[MAX_SIZE];

int cnt = 1;
int N, M;

void dfs(int v)
{
	check[v] = true;

	for (int i = 1; i <= N; i++) {
		if (map[v][i] && !check[i]) {
			cnt++;
			dfs(i);
		}
	}
	total[v] = cnt;
}


int main(void)
{
	int v1, v2;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d", &v1, &v2);
		map[v2][v1] = 1;
	}

	for (int i = 1; i <= N; i++) {
		memset(check, 0, sizeof(check));
		cnt = 1;
		dfs(i);
	}

	int max = -1;
	for (int i = 1; i <= N; i++) {
		if (max < total[i])
			max = total[i];
	}

	
	for (int i = 1; i <= N; i++) {
		if (max == total[i]) {
			printf("%d ", i);
		}
	}

	return 0;
}

ydk1104 5년 전 0

간선을 배열로 저장하는 대신 링크드리스트로 저장해보세요

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

문제

문제

출처

ICPC

1325 : 메모리 초과 문제를 어떻게 해결해야할까요?...

gksehdgh94 5년 전 0

ydk1104 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말