heeStory

문제링크:  https://www.acmicpc.net/problem/1967 가중치가 제일 큰 값을 가진 지름을 찾는 문제 문제에서 주어진 조건노드 번호 순서대로 주어짐첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호 접근원은 두 점(말단 노드) 사이 길이이다그 중 제일 긴 노드 두 점을 찾으면 된다DFS를  사용하면 시작 노드에서부터 가장 큰 말단 노드를 찾을 수 있다. 현재 어떤 노드가 제일 큰 노드인지 알 수 없으니 최상위 부모 노드에서 시작하여  가장 큰 말단 노드부터 찾는다.  1번. DFS로 말단 노드 한 점을 찾는다.최상단 노드는 제일 사이즈가 큰 말단 노드가 아니다. 따라서, 최상위 노드에서 경로가 가장 긴(지름이 제일 긴) 노드를 찾자.1번 노드는 그저 처음 탐색을 위한 노..

BFS & DFS 문제를 풀다보면, 메모리 초과가 발생할 때가 있다. 대부분 메모리 초과의 이유는 Stack에 담기는 요소가 계속해서 중복값을 넣고 제대로 필터링을 하지 않아서 발생한 문제이다. Visited 의 위치가 중요하다. 다음 코드를 보자, visited 선언에 따라서 결과가 다르게 반영된다. 자세하게 보자, 첫번째의 경우 만약 , Queue에 Node 1 , 2 , 3, 4 가 들어있는 상황에서 Node 1이 꺼내져서 bfs를 한다고 해보자, 그리고, Node 1 에서 갈 수 있는 Node는 Node 2 , Node 3이라고 하자. Node1 이 bfs를 하면서 Node 2가 당연히 아직 큐에 있으니, Visited[Node2] 는 false 이므로 또 넣게 되는 불상사가 생긴다. 큐에 있는 ..