꼬리에 꼬리를 무는 형태이므로, 오일러 경로를 의심해 볼 수 있다. 동일한 컴포넌트 안에서 해당 정점과 연결된 간선이 홀수인 정점의 개수가 2k이면, 한붓그리기로 최소 k개의 경로로 만들 수 있음은 오일러 경로의 증명을 통해 논증할 수 있다. 다만, 오일러 회로의 경우, 해당 점점과 연결된 간선이 홀수인 정점의 개수가 0개임에도 불구하고 최소 1개의 경로로 만들 수 있으므로 예외처리 해야 한다. 즉, 해당 컴포넌트에서 최소경로는 max(해당 점점과 연결된 간선이 홀수인 정점의 개수 / 2, 1)이다. 또한 다른 컴포넌트간에는 따로 따져서 최소값끼리의 덧셈을 통해 구해주면 된다. 추가적으로 동일한 컴포넌트에 위치하고 있는지는 dfs와 visited배열을 활용해서 처리해주면 된다. #include #defi..