출처 : https://www.acmicpc.net/problem/1967

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1967.cpp


이 문제는 다풀어놓고 한참을 틀렸던 문제이다. 어처구니 없이 모든걸 만들어놓고 틀렸다 ㅠㅠ 왠지 작년에 본 삼성 SW역량 시험이 생각났다.. 다만들고 문장하나를 생각하지 못했던...

아무튼 문제는 가장 긴 구간을 찾는것이다. 

당연히 어떤 구간이 긴지 모르므로 전부 검색해봐야한다.

나는 DFS를 활용하였다. 여기서 내가 놓친 부분이 그것이다. 최대 지름을 구하는 문제이므로 2개의 길이만 필요하다. 

그리고 문제에서는 이진트리 느낌으로 보여졌는데, 실제 데이터에는 이진트리가 아닌것들도 많다. 자식노드가 여러개인경우 말이다.

사실 이정도면 미리 문제에서 알려줘야하지 않나..싶다.

알고리즘은 다음과 같다.


1. 벡터를 사용하여 연결된노드와 값을 입력한다.

2. 함수를 호출하는데 인자는 루트노드만 보내준다.

3. 각 루트노드에서 연결된 간선을 전부 탐색하고 그 간선의 값을 더해본다. 

4. 그리고  temp와 val[2]를 활용하여 val[2] 에는 가장 긴 2개의 녀석만 담아둔다.

5. 그 2개의 값의 합이 ans보다 큰지 비교를 한다.

6. 리턴은 그 2개에서 가장 긴녀석을 리턴한다.


이 과정이 반복이되면 딱 한번 모든 노드를 검색하게 되고 자연스레 답이 담기게 된다.

뭐랄까..예전엔 이런 DFS가 조금 힘들었는데 이젠 뭐...그냥 술술 풀린다. 그래도 실수한건 실수한거다. 문제를 잘 읽어야겠다.

'Algorithm' 카테고리의 다른 글

[AC] 10827 a^b  (0) 2016.08.18
[AC] 11057 오르막 수  (0) 2016.08.03
[AC] 9935 문자열 폭발  (0) 2016.08.03
[AC] 1613 역사  (1) 2016.08.03
[AC] 1298 노트북의 주인을 찾아서  (0) 2016.08.03

+ Recent posts