1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 이해 & 기본 개념 특정 노드 2개를 잡고 양쪽으로 당겼을 때, 가장 길게 늘어나는 경우를 트리의 지름이라 한다. dfs를 수행해서, 각 노드의 자식들 중 가장 큰 가중치 + 자신의 가중치를 리턴한다. 갈라지는 부분에선, 해당 노드가 중심이 될 수 있는 가능성이 있기에, 자식들의 가중치의 합 중 가장 큰 2개를 구해서 max와 비교한다. 양쪽으로 잡아 당길 때, 두 개를 잡고 당기기 때문에 상위 가중치 2개를 선택 중요 포인트 이진 트리..
9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 이해 & 기본 개념 n 명의 학생이 각각 같이 팀이 되고 싶은 학생을 1명씩 선택한다. 학생들을(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 학생들이 선택한 결과가 주어질 때, 팀에 속하지 않는 학생의 수를 구하는 문제 중요 포인트 선택한 학생들끼리 사이클을 이루는 경우가 팀이 되는..
16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 문제 이해 & 기본 개념 그래프와 방문 순서가 주어진다. 해당 그래프에서 입력받은 순서가 dfs로 방문 가능한지를 체크하는 문제 해당 문제는 방문 순서에 대한 기준을 두지 않았다. 즉, 어떤 순서로 방문을 해도 dfs로 방문 가능한 순서이기만 하면 된다. 중요 포인트 n이 10만까지 들어오므로, dfs를 완전히 수행하면 시간 초과 dfs로 접근하되, 수행 시간을 줄여아한다. 최종 풀이 dfs의 경우 여러 자식들 중 어떤 자식을 ..
