티스토리 뷰

ICPC/2014 인터넷예선

C. 그리드 그래프

전명우 2014. 10. 7. 17:57

문제에서 $m \times n$ 크기의 토로이드 그래프를 정의한다. 이 토로이드 그래프에서 해밀턴 회로를 찾는 것이 문제다. 문제 조건에서 $m, n \geq 3$ 이므로 모든 $m \times n$ 크기의 토로이드 그래프에서 해밀턴 회로가 존재함을 알 수 있다.


i) m이 짝수일 때,


ii) m이 홀수일 때,



위와 같이 이동하면 해밀턴 회로가 된다.


'ICPC > 2014 인터넷예선' 카테고리의 다른 글

G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
C. 그리드 그래프  (2) 2014.10.07
B. Driving License  (1) 2014.10.07
A. ACM 호텔  (0) 2014.10.07
댓글
  • 프로필사진 지윤 명우님.. 제가 이번에 ACM-ICPC 온라인 예선을 치르기 위해 명우님 블로그를 매일같이 드나듭니다.. 항상 감사드리구여!!
    다만, 이번 문제에서 이해가 안되는 것이 토로이드 그리드에서 해밀턴 사이클 경로가 있는지 확인하기 위해 홀수 짝수 나누어 상황을 그려주셨는데 저 경로는 어떻게 알아내신건가요? 원래 해밀턴경로가 존재하는지 알기 위해선 홀수일때와 짝수일때 경우 두개로 나눠서 경로 규칙을 알아내나요?
    2016.09.21 19:28
  • 프로필사진 전명우 안녕하요.
    모든 문제에 대해서 짝수, 홀수 나눠서 생각하는 것이 아니며, 토로이드 그래프에서 해밀턴 회로를 익히고 있는 것도 아닙니다.
    다만, 문제를 보고 예제를 그려서 해밀턴 회로가 어떤 패턴?을 갖는지 생각해보고 모든 경우에 대해서 가능한지 생각해봤습니다. 그랬더니, 홀수랑 짝수랑 경우가 나누어지는 것을 알게 된 것이구요.
    도움이 되었으면 좋겠네요.
    2016.09.28 09:28 신고
댓글쓰기 폼