[일반] 아래 그래프문제 다른 아이디어입니다.

[익명(211.179)]

특별한 점중 하나(A)를 고릅니다.

이 특별한 점에서 1칸 움직여 갈수 있는 점들을 관찰합니다.

이중 특별한 점이 없다면, 한번 더합니다. 이를 반복합니다.

만약 특별한 점(B)이 있다면, 그만움직이고 A와 B를 연결해줍니다.

이는 최단거리일것입니다.

이와같은 과정을 B에서 다시 시작합니다.

이를 반복하면 비록 귀찮기는해도, ABCDE가 모두 최단거리로 연결될 것 같은데요. 이는 반례가 없을까요?

[익명(175.223)]

모든점들끼리 연결된 그래프의 경우에 점 두개가 집합 S에 포함이 안되면 알고리즘따라 반례가 생길듯 - dc App

[dd(110.12)]

A,B,C,D,E가 서로 연결되어있지 않다고 하고 A,B,C,D,E 모두와 연결된 vertex 가 u랑 v 두개 있다고 하면 알고리즘이 minimum distance path중에 뭘고르냐에 따라 u랑 v가 둘 다 포함되는 subgraph를 결과로 줄 수 있는 것 같은데 그러면 u,A,B,C,D,E로 만들어지는 induced subgraph보다 edge 갯수 많아져서 안되는거같은데