안녕하세요.
눈팅을 주로하는 탑코더 Rating 800점대의 유저입니다. :-)
다름이 아니라 최근 알고리즘 공부겸 예전 ICPC 문제를 풀고있는데여.
2006년 문제를 푸는 중 J번에서 난관에 부딧혀 질문을 올립니다.
경로는 여기구여, http://acm.kaist.ac.kr/Problems/2006j.pdf
대충 요약해보면 건널 수 있는 통나무의 최대치를 구하되,
1. 시작 통나무와 마지막 통나무가 동일해야하며
2. 통나무는 한번씩만 건널 수 있으며
3. 통나무는 겹치는 영역이 존재시 수작으로 이동할 수 있다는 것입니다.
저는 이 문제를 건널 수 있는 통나무들을 edge로 구성한 뒤, 최대 Cycle을 구하면 풀 수 있다고 생각했는데요.
Cut Vertex를 구하는 방식을 응용하면 최대 Cycle을 찾을 수 있다고 생각했는데, 이부분에 아이디어가 잘 안떠오르네요.
제 방법이 맞는지, 아니면 다른 간단한 방법이 있는지 알고 싶습니다.
그리고 그래프에서 최대 Cycle을 구하는 방식을 알 수 있을까요?
dgsquare
안녕하세요.
눈팅을 주로하는 탑코더 Rating 800점대의 유저입니다. :-)
다름이 아니라 최근 알고리즘 공부겸 예전 ICPC 문제를 풀고있는데여.
2006년 문제를 푸는 중 J번에서 난관에 부딧혀 질문을 올립니다.
경로는 여기구여,
http://acm.kaist.ac.kr/Problems/2006j.pdf
대충 요약해보면 건널 수 있는 통나무의 최대치를 구하되,
1. 시작 통나무와 마지막 통나무가 동일해야하며
2. 통나무는 한번씩만 건널 수 있으며
3. 통나무는 겹치는 영역이 존재시 수작으로 이동할 수 있다는 것입니다.
저는 이 문제를 건널 수 있는 통나무들을 edge로 구성한 뒤, 최대 Cycle을 구하면 풀 수 있다고 생각했는데요.
Cut Vertex를 구하는 방식을 응용하면 최대 Cycle을 찾을 수 있다고 생각했는데, 이부분에 아이디어가 잘 안떠오르네요.
제 방법이 맞는지, 아니면 다른 간단한 방법이 있는지 알고 싶습니다.
그리고 그래프에서 최대 Cycle을 구하는 방식을 알 수 있을까요?
16년 전