BOJ 28104 - 삼각형 모험
$2NM$ 개의 정점이 있다고 생각하자.
각 정점은 최대 degree $\le 2$ 이기 때문에 항상 그래프는 일자로 된 직선이거나 원형 싸이클이다.
여기서 뇌절해서 나는 LCA까지 섞어서 풀었는데, 다음과 같이 DFS로 풀 수 있다.
$u, v$가 같은 컴포넌트에 속하지 않는다면 $-1$ 이고,
그래프가 일자로 된 직선이라면 차수가 $1$ 인 지점부터 시작해서 최단거리를 기록하면 되고,
그래프가 싸이클이라면 아무데서나 시작하고, 한바퀴 돌았을 때가 더 거리가 최단이라면 정답에 갱신하고 출력해주면 된다.
그냥 풀어도 구현이 많은편이다.
Comments