글 읽기 - 해결하고 싶습니다.

johyesong8686 4년 전 0

처음에는

1번 방식으로 풀었는데 시간 초과가 났습니다.

그래서

2번방식<최대 길이의 인덱스를 구해서 시작함)

으로 풀었는데 틀렸습니다.

2번 방식이 틀린 것이라면 1번 방식에서 어떤 점을 수정하면 좋을 까요

아니면 다른 논리가 있을까요 ?

</////1번 코드///////>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 10001
using namespace std;
int N;
int len = 0;
vector <pair <int, int > >a[MAX];
int visited[MAX];
int check[MAX];
void bfs(int start){
	queue <int> q;
	q.push(start);
	check[start]=1;
	//cout <<"Start:" <<start<<'\n';
	while(!q.empty()){
		int start=q.front();
		q.pop();
		for(int i=0; i<a[start].size();i++){
			if(visited[a[start][i].first]==0&&check[a[start][i].first]==0){
				check[a[start][i].first]=1;
				visited[a[start][i].first]=visited[start]+a[start][i].second;
				q.push(a[start][i].first);
				//cout <<"push: "<<a[start][i].first<<'\n';
				//cout <<"가중"<<visited[a[start][i].first]<<'\n';
			}
			
			if(len <visited[a[start][i].first]){
				len=visited[a[start][i].first];
			}
		}
	}
}
int main(void) {
	int N;
	cin >>N;
	for(int i=1;  i<=N;i++){
		int x;
		cin >>x;
		while(1){
		int y,z;
		cin >>y;
		if(y==-1){
			break;
		}
		cin >>z;
		a[x].push_back(make_pair(y,z));
		
	}
		
	}
	for(int i=1; i<=N;i++){
		memset(visited,0,sizeof(visited));
		bfs(i);
	}
	cout <<len <<'\n';
	



	return 0;
}

<////////2번코드 ///////>
    #include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 100001
using namespace std;
int N;
int len = 0;
vector <pair <int, int > >a[MAX];
int visited[MAX];

void bfs(int start){
	queue <int> q;
	q.push(start);
	visited[start]=0;
	while(!q.empty()){
		int start=q.front();
		q.pop();
			//cout <<"Start:" <<start<<'\n';
		for(int i=0; i<a[start].size();i++){
			if(visited[a[start][i].first]==-1){
				visited[a[start][i].first]=visited[start]+a[start][i].second;
				q.push(a[start][i].first);
				//cout <<"push: "<<a[start][i].first<<'\n';
				//cout <<"가중"<<visited[a[start][i].first]<<'\n';
			}
			
			if(len <visited[a[start][i].first]){
				len=visited[a[start][i].first];
			}
		}
	}
}
int main(void) {
	int N;
	int index;
	int max_len;
	scanf("%d",&N);
	for(int i=1;  i<=N;i++){
		int x;
		scanf("%d",&x);
		while(1){
		int y,z;
		scanf("%d",&y);
		if(y==-1){
			break;
		}
			scanf("%d",&z);
		a[x].push_back(make_pair(y,z));
		
	}		
	}
	
		memset(visited,-1,sizeof(visited));
		bfs(index);
	
	printf("%d",len);
	//cout <<len <<'\n';
	

	return 0;
}

ha_ram 4년 전 2

트리의 지름은 bfs 단 두번으로 구하는 멋진 알고리즘이 있습니다.

인터넷에 검색해보시고 공부해보시길 추천합니다.

화이팅하세요!

johyesong8686 4년 전 1

감사합니다!

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

문제

문제

출처

ICPC

해결하고 싶습니다.

johyesong8686 4년 전 0

ha_ram 4년 전 2

johyesong8686 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말