| [ KAIST ] in KIDS 글 쓴 이(By): ryecomp (바람돌이) 날 짜 (Date): 2002년 3월 27일 수요일 오후 07시 57분 49초 제 목(Title): [질문] 그래프 문제입니다... 일단 하나의 graph가 있다고 합시다. 이 graph는 undirected & connected 되어 있구요. 이 graph는 N개의 node로 구성되어 있는데 각 node의 이름을 a1, a2, ... , aN이라고 합시다. 지금 바둑알 M개 (M < N) 가 있는데 이 바둑알에 각각의 이름을 b1~ bM라고 표기한 후 M개의 바둑알을 위 graph의 임의의 node에 겹치지 않게 (하나의 node에는 둘 이상의 바둑알을 놓지 않는다.) 배치한 후, 바둑알을 인접한 node로 움직여 (물론 이 인접한 node가 비어있을 시만 움직일수 있고, 서로 연결되어 있어야 겠죠) a1-b1, a2-b2, ... aM-bM과 같이 배치하는 일반적인 알고리즘이 있습니까 ? 그 이름이라도 알려주시면 ... 감사 감사.. |