http://www.spoj.com/problems/PT07Z/
อธิบายโจทย์
ถ้ามี Tree ที่ unweighted, undirected มี N nodes จงหาเส้นทางที่มีความยาวที่สุด
ลองสังเกต
unweighted คือไม่มีการถ่วงน้ำหนักทุกเส้นมีระยะทางเท่ากันหมด undirected คือเส้นแต่ละเส้นไม่มีลูกศร หมายความว่า ถ้า A เชื่อม B เราสามารถเดินจาก A->B หรือกลับ B->A ได้
รูป 1.1
รูป 1.2
ถ้าเรามองรูป 1.2 เราอาจจะอยากตอบว่าเส้นทางที่ยาวที่สุดคือเส้นสีแดงหรือสีน้ำเงิน แต่จริงๆแล้วถือว่าผิด เพราะกราฟนี้เป็น undirected ถ้าวาดกราฟนี้ใหม่ให้เป็นแบบนี้
รูป 1.3
กราฟของเราก็จะมีความยาวเพิ่มจาก 2 เป็น 3
เราจะแก้ปัญนี้อย่างไร
ถ้าเราเริ่มต้นที่ 1 แล้วทุกครั้งที่เราขยับไป node อื่นถือว่าเราเดิน 1 ก้าว เราจะได้เป็นรูปนี้
รูป 1.4
ถ้าเราเลือกไป 0 เราจะได้ 2 ต่อมาเรายังเลือกได้อีกเส้น เราจะเลือกเส้นที่ไป 3 หรือ 4 ก็ได้ เพราะมีค่าเท่ากันคือ 1 เราเอา 2 + 1 จะได้ 3 คำตอบทางที่ยาวที่สุดคือ 3 เราไม่ต้องรวม 1 เพราะว่าตัวที่เป็น leaf จะไม่ถูกนับ ถ้าเรารวม 1 เราต้องลบออก 1 เพราะว่าเราได้นับ leaf ไปแล้ว เช่น ถ้าเราเลือกไป 0 กับ 4
เราจะได้รูปนี้
รูป 1.5
เราได้นับ 0 4 2 แต่เราไม่ได้นับ 1 ซึ่งเท่ากับ 3 หากเรานับ 1 จะเป็น 1 4 0 2 ซึ่งเท่ากับ 4 แล้วเราต้องลบ leaf ออก 4 - 1 = 3 ซึ่งทำให้เราไม่จำเป็นที่จะต้อง 1 รวมไปก็ได้
เราจะทำแบบที่เราคิดได้อย่างไร
ถ้าเรา dfs(1) เราจะสามารถขยับเข้าไปปลาย tree นี้ได้ทีละเส้นๆ ตาม algorithm ของ dfs แต่ละครั้งที่เราขยับ เราจะ +1 เมื่อเราถึงทุกปลายแล้ว เราจะ backtrack กับมาที่ 1 แล้วเลือกเส้นที่มากที่สุดมาสองเส้น
การที่เราเลือกมากที่สุดมาสองเส้นหมายความว่าเรากำลังจะเลือก ตัวมากสุดตัวแรก กับตัวมากสุดตัวสอง ซึ่งตัวมากสุดตัวแรกสามารถมีค่าเดียวกับตัวสองได้
เขียนเป็น code ได้แบบนี้
ซึ่งก็คือ dfs ธรรมดาๆ แค่มีการดูว่าตัวไหน max1 max2 และเวลา return ถ้าไม่ใช่ node ที่เราใส่ไปตอนแรกก็จะ return ค่า max1 ออกไป เรา return max1 เพราะจะได้ทางที่ยาวสุด ถ้า return max2 จะได้ทางที่ยาวรองลงมา
ไม่มีความคิดเห็น:
แสดงความคิดเห็น