1967번 - 트리의 지름
대략 알고리즘은
1. 아무점 (여기선 정점 1을 루트라고 했으니 1)을 잡고 bfs를 수행하여 가장 먼 정점을 찾습니다.
2. 1.에서 찾은 정점을 토대로 bfs를 수행하여 다시금 가장 먼 정점과의 거리를 계산하여 출력합니다.
입니다..
DD구조체는 가장 먼 정점을 담을 정점의 번호와 그 거리값을 가집니다.
제출하자마자 틀렸다고는 뜨는데 어디가 잘못된건지 잘 모르겠어요 ㅠㅠ
도움이 될진 모르겠지만, 정점이 8300개인 반례 하나 드립니다.
https://doyak.s-ul.eu/cU2LvUpF
정답은 235인데, 0이 출력됩니다.
26번째 줄 코드를 25번째줄 앞에 놓아야 될것 같습니다.
그리고 배열 C를 BFS한번 후에 다시 초기화 시켜주셔야 합니다.
제가쓴 첫 댓글은 무시해주세요 ㅎㅎ
잘못 생각했네요
memset은 자료형을 알지 못합니다. 오직 바이트 단위로만 세팅해줍니다. 따라서 10001이라는 건 10001바이트를 의미하는 것이지, int형 10001개의 크기가 아닙니다.
memset -> for문으로 대체하여 초기화하여 해결했습니다!
dim03178// 반례 감사합니다. 이 데이터로 해결했습니다 ㅠㅠ
lyzqm// memset으로 초기화 했다고 생각했는데 이유를 모르겠지만 제대로 초기화가 되지 않았더군요. 댓글 감사합니다!
추가적으로 memset이 제대로 동작하지 않은거같은데 정확한 이유를 알 수 있을까요,,??
djm03178// 답글 감사합니다.. 제가 기초적인 걸 제대로 공부안하고 있엇네요 ㅠㅠ 다시 한 번 감사해요 :)
윗분이 잘 설명해주셨네요
memset(C, 0, sizeof C);
sizeof를 붙여서 초기화 시켜주시면 됩니다
댓글을 작성하려면 로그인해야 합니다.
adh0463 6년 전
대략 알고리즘은
1. 아무점 (여기선 정점 1을 루트라고 했으니 1)을 잡고 bfs를 수행하여 가장 먼 정점을 찾습니다.
2. 1.에서 찾은 정점을 토대로 bfs를 수행하여 다시금 가장 먼 정점과의 거리를 계산하여 출력합니다.
입니다..
DD구조체는 가장 먼 정점을 담을 정점의 번호와 그 거리값을 가집니다.
제출하자마자 틀렸다고는 뜨는데 어디가 잘못된건지 잘 모르겠어요 ㅠㅠ