글 읽기 - 시간초과가 발생하는데 로직의 문제점을 잘 모르겠습니다.

cocoon 3년 전 0

parent 2차원 배열로 2의 j승 위에있는 부모노드들을 기록한 다음 logN의 복잡도로 구현을 하였는데 시간초과가 발생하는 이유가 궁금합니다 ㅜ.ㅜ

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int N, M;
int u, v;
queue<int> q;
vector<int> node[100001];
bool check[100001];
int parent[100001][20];
int depth[100001];

int LCA(int u, int v)
{
	// v가 u보다 더 깊은 노드로 세팅
	if (depth[u] > depth[v]) swap(u, v);

	// 두 노드의 깊이가 같아질때까지 v노드는 위로 거슬러 올라감
	while (depth[u] != depth[v])
	{
		// 두 노드의 깊이 차이
		int dist = depth[v] - depth[u];

		for (int i = 0; i < 20; i++)
		{
			if (dist <= (1 << i))
			{
				// 2^i 만큼 거슬러 오라감
				v = parent[v][i];
				break;
			}
		}
	}

	// 두 노드가 같아질때 까지 위로 거슬러 올라감
	while (u != v)
	{
		for (int i = 0; i < 20; i++)
		{
			if (parent[u][i + 1] == parent[v][i + 1])
			{
				u = parent[u][i];
				v = parent[v][i];
				break;
			}
		}
	}
	return u; // LCA 리턴
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	// 해당노드에 연결된 노드 push
	for (int i = 0; i < N - 1; i++)
	{
		cin >> u >> v;
		node[u].push_back(v);
		node[v].push_back(u);
	}

	check[1] = true;
	q.push(1); // 트리의 루트 

	while (!q.empty())
	{
		int x = q.front(); // 부모 노드
		q.pop();

		for (int i = 0; i < node[x].size(); i++)
		{
			int child = node[x][i];

			if (!check[child]) // 현재노드를 방문한적 없다면
			{
				depth[child] = depth[x] + 1; // 깊이 +1
				check[child] = true; // 방문표시
				parent[child][0] = x;
				for (int j = 0; j < 20; j++) // 부모노드 입력
				{
					// 현재노드에서 2^(j+1) 위에 있는 부모 노드는 
					// 2^j 위에 있는 부모노드의 2^j 위에 있는 부모노드
					parent[child][j + 1] = parent[parent[child][j]][j];

					// 2^(j+1) 위에 부모노드가 없을 경우
					if (parent[child][j + 1] == 0) break;
				}

				q.push(child); // 큐에 추가
			}
		}
	}

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> u >> v;
		cout << LCA(u, v) << '\n';
	}

}

kth990303 3년 전 2

21~35번째 줄의 v가 거슬러 올라가는 코드에서 오히려 u보다 높이 올라가버릴 수 있습니다.

이 테스트 케이스를 한 번 넣어서 디버깅해보시는 걸 추천드려요.

30
2
3
4 
5 
6 
7 
8 
9 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
11
    
ans: 6
wrong: TLE (v가 0번 루트까지 무한히 올라가며, 무한루프를 돌음)

cocoon 3년 전 1

v가 u를 넘어설거라는 생각도 못했네요 저번에도 시간초과코드 도움주셨는데 이번에도... 정말 감사드립니다!

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

문제

문제

출처

ICPC

시간초과가 발생하는데 로직의 문제점을 잘 모르겠습니다.

cocoon 3년 전 0

kth990303 3년 전 2

cocoon 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말