글 읽기 - 이문제 DFS나 BFS로 시간안에 돌아갈까요?

sgc109 7년 전 0

대략 (40000 + 39999) * 10000 으로 대략 8억번정도 돌것같은데 2초안에 무리겠죠..?

알고리즘을 좀더 개선시키기위해 어떤방법이있나요?

orange4glace 7년 전 1

(LCA)Lowest Common Ancestor 라는 알고리즘을 이용해서 푸시면 됩니다.

https://en.wikipedia.org/wiki/Lowest_common_ancest...

https://www.topcoder.com/community/data-science/da...

sgc109 7년 전 0

@orange4glace 이 문제에서는 따로 부모자식관계가 없지않나요?

orange4glace 7년 전 1

이 문제의 데이터는 트리 데이터이기 때문에 1번 정점을 ROOT 노드라고 생각하여 높이가 0이라고 보면,

1번 노드부터 DFS를 돌리면, 1번 노드에 연결된 노드들은 1번 노드의 자식이 되고, 그 노드들의 높이는 1이라고 볼 수 있습니다.

결과적으로 DFS 탐색을 마치게되면 1번 노드가 ROOT 노드인 트리 데이터를 parent 배열 등을 통해 표현할 수 있게 됩니다.

int depth[N];
int visit[N];
int parent[N];

void dfs(int n, int dep) {
	depth[n] = dep;
	visit[n] = true;

	for (int i = 0; i < v[n].size(); i++) {
		int u = v[n][i];
		if (visit[u]) continue;
        parent[u] = n;
		dfs(u, dep + 1);
	}
}

int main() {
    dfs(1, 0);
}

sgc109 7년 전 0

@orange4glace 그러니까 부모 자식관계가 명시되어있지않으므로 여러가지 모양의 트리가 가능한데 그냥 1번을 루트로 삼아서 만든 트리로 푼다는거죠??

orange4glace 7년 전 1

넵 그렇습니다

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

문제

문제

출처

ICPC

이문제 DFS나 BFS로 시간안에 돌아갈까요?

sgc109 7년 전 0

orange4glace 7년 전 1

sgc109 7년 전 0

orange4glace 7년 전 1

sgc109 7년 전 0

orange4glace 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말