일상생활/끄적끄적

수1 그래프 문제의 변환



수1 그래프 문제를 풀어보다가 생각난 풀이법입니다.
컴퓨터 프로그래밍 쪽 알고리즘 책을 뒤져보면서 알게된 트리 정렬 방식, 최단경로 이동방식과 기타 자질구레한 저의 생각을 합쳐서 풀어봤는데요.

만약에 문제가 출발 원점으로 각 지점을 1번씩 거치는 거라면 원점을 2개로 나누어서 스타팅 포인트와 피니시 포인트로 생각하는 겁니다. 그리고 각 지점간의 관계를 생각해서 어떤 식으로 이동할 수 있는지에 대해서 생각해 보는거죠. 일단 A-B-D의 환형 구조를 띄고 있고 C는 A를 통해서만 갈 수 있음으로 C는 스타팅 포인트에서 바로 가야하거나, 아님 C에서 피니시 포인트로 가야합니다. (그건 생각해보시길...)

그걸 이용해서 이동할 수 있는 경로를 제한할 수 있고 선 그어가면서 삽질 할 필요가 없어집니다. 어때요 참 쉽죠?