말하는 컴공감자의 텃밭

도시 분할 계획  마을에는 경로가 존재하고, 분리해서 이 경로를 없애면서 유지비용을 최대한 줄이는 문제다.마을 내부에서 서로 다른 집을 방문할 수 있어야하고, 마을이 분리됐다면 분리된 마을끼리는 연결되지 않아도 된다.이게 말로만 풀어쓰니까 이게 무슨..? 싶은데 그림으로 정리하면 편하다. 파란 부분을 A마을, 붉은 부분을 B마을이라고 하자,A 마을끼리 모두 연결되어 있고, B 마을끼리 모두 연결되어 있다.A와 B 마을 사이에 연결되는 부분이 오늘 문제의 포인트다.분할되는 부분이기 때문에 유지비가 들지 않는다.그림을 다시보면 모든 점이 연결된 그래프고, 우리는 유지비를 최소한으로 유지하고 싶으므로많은 경로가 존재한다면 그 중 유지비가 적은 값으로 연결을 시켜야 할것이다. 결국 이건 학부때 배웠던 최소 스패..