elvpfhhrm   6달 전

고수님들의 조언을 부탁드립니다.

질문 게시판을 돌아다니며 더 좋은 풀이법을 보았지만 아무래도 제 코드의 문제점이 알고 싶어 질문을 남깁니다.

입력받은 간선 정보로 priority_queue를 사용해 sparseTable 테이블을 만들었습니다. 

일단 예제와 질문게시판에 찾은 반례 2개는 정답이 나왔습니다만 제출하자 마자 '틀렸습니다'를 받았습니다.

어느 부분이 잘못돼서 오답이 나오는지 알려주실 수 있으신가요?

bnb2011   6달 전

오류가 나는 이유는,

1. Sparse Table의 크기가 충분하지 않습니다. 정점의 깊이는 최대 10만까지 될 수 있고, 현재 2^(n-1)번째 조상 노드를 SparseTable[1]에 저장하고 있으니 크기는 최소 [18][MAX]이 되어야 합니다.

2. 따라서 두 정점간 깊이의 차이도 최대 99999까지 될 수 있습니다. 41번째 줄을 지워야 합니다.

3. 두 정점의 깊이가 다를 때 깊이를 맞춰주는 과정이 잘못되었습니다. 현재 SparseTable[n][cur]에는 cur 정점의 2^(n-1)번째 조상이 저장되어있기 때문에, 2^k <= differ를 만족하는 가장 큰 k에 대해, FindParent(one, SparseTable[k+1][two])와 같은 형식으로 재귀호출이 이루어져야 합니다.

그리고 틀린 건 아니지만... 고치면 좋을만한 점들을 몇 개 짚어드립니다.

1. 정점을 순회할 때 Dijkstra를 사용할 이유가 없습니다. 모든 정점 사이의 거리가 같기 때문에 BFS로도 충분합니다.

2. 1번 노드의 부모를 1로 설정하면, 91번째 줄과 같은 예외처리를 할 필요가 없습니다.

3. 19~21번째 줄을 swap(one, two)로 대체할 수 있습니다.

elvpfhhrm   6달 전

감사합니다

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