수1 그래프 문제를 풀어보다가 생각난 풀이법입니다.
컴퓨터 프로그래밍 쪽 알고리즘 책을 뒤져보면서 알게된 트리 정렬 방식, 최단경로 이동방식과 기타 자질구레한 저의 생각을 합쳐서 풀어봤는데요.
만약에 문제가 출발 원점으로 각 지점을 1번씩 거치는 거라면 원점을 2개로 나누어서 스타팅 포인트와 피니시 포인트로 생각하는 겁니다. 그리고 각 지점간의 관계를 생각해서 어떤 식으로 이동할 수 있는지에 대해서 생각해 보는거죠. 일단 A-B-D의 환형 구조를 띄고 있고 C는 A를 통해서만 갈 수 있음으로 C는 스타팅 포인트에서 바로 가야하거나, 아님 C에서 피니시 포인트로 가야합니다. (그건 생각해보시길...)
그걸 이용해서 이동할 수 있는 경로를 제한할 수 있고 선 그어가면서 삽질 할 필요가 없어집니다. 어때요 참 쉽죠?
'일상생활 > 끄적끄적' 카테고리의 다른 글
| 블로그 수리 개시 (0) | 2010.05.03 |
|---|---|
| 시험 끝 (0) | 2010.04.30 |
| 시간에 쫒겨서 그리고 시간을 바라보면서... (2) | 2010.04.21 |
| 재미있는 유입로그 (0) | 2010.04.04 |
| 주변 분들이 하나 둘씩 떠나가는군요. (2) | 2010.04.01 |
| 정보기기운용기능사 시험 보고 왔습니다. (3) | 2010.03.28 |
| 마이크로 블로그 OTL (11) | 2010.03.28 |
