백준 1167, 1967 트리의 지름 혼내주기
두 문제는 출력 형식만 다른 같은 문제다. 심지어 이름도 같다. 하나를 풀고 까먹을때쯤 다른 하나를 풀었어야 하는데, 눈앞에 꽁짜 경험치를 참지 못했다... 문제를 딱 읽었을 때 방법이 떠오르지 않아서 시간초과가 분명함에도 모든 정점에서 bfs를 돌렸다. 물론 시간초과. 도저히 떠오르지 않아서 좀 찾아보니 구사과님의 블로그에 트리의 지름을 구하는 잡기술이 있었다. 1. 트리에서 임의의 정점 u에서 가장 먼 정점 v를 찾는다. 2. 정점 v에서 가장 먼 정점 w를 찾는다. 정점 v와 w를 찾았다면 트리의 지름은 v와 w의 거리이다. 남은 부분을 뚝딱하면 문제 해결. #include #include #include using namespace std; vector adj[100001]; //vertex di..
혼내주기
2021. 8. 2. 00:02