[Project Solution] Graph: ภาคขยายอาณาเขต … step by step

บทความนี้ย้ายมาจาก nartra.blogspot.com อยู่ในช่วงรีไรท์นะ

พอดีช่วงนี้กำลังอ่าน "หงสาจอมราชันย์" อยู่ เลยแต่งโจทย์ให้เป็นเรื่องสามก๊กซะเลย (ฮา)

เรื่องมีอยู่ว่า

ใน ยุคสามก๊ก, ขงเบ้ง (หรือพิสดารเจ็ด) ต้องการขยายดินแดน ขงเบ้งเลยต้องการส่งทหารไปปราบก๊กอื่นๆ ที่ตั้งตัวเป็นใหญ่อยู่ (พูดง่ายๆ คือไปบุกยึดนั้นแหละ) โดนสืบทราบมาว่าในพื้นที่โดยรอบเมืองเกงจิ๋วซึ่งเป็นของฝ่ายขงเบ้งเป็นดัง แผนที่ข้างล่าง

เนืองจากถ้าใช้ชื่อเมืองเป็นภาษาจีนจะทำ ให้ยากในการเรียก เราเลยเรียกชื่อเมืองเป็นตัวอักษรภาษาอังกฤษแทน (ฮา) โดยมีเกงจิ๋วอยู่มุมซ้ายบนของแผนที่ที่ตำแหน่งเมือง A

ตัวเลขที่เขียนกำกับอยู่แต่ละเมืองนั่นคือ "เกจพลังทหาร" ของแต่ละเมืองนั่นเอง


แต่การทำศึกต้องมีแผนการ! ขงเบ้งได้คิดไว้เรียบร้อยแล้วโดยมีกฎดังนี้

  1. ขบวนทัพจะต้องเดินทางตามเส้นทางเท่านั้น ... ออกนอกเส้นทางมีโอกาสโดนลอบโจมตี
  2. ใน 1 วัน เดินทางได้แค่ระยะ 1 เมืองเท่านั้น เมืองที่เหลือจะเอาไว้บุกในวันถัดไปๆๆ ... โดยที่เมืองที่ยึดมาได้จะถูกใช้เป็นฐานทัพใหม่เพื่อบุกเมืองต่อไป แบบนี้ไปเรื่อยๆ (ฐานทัพเริ่มแรกจะใช้เมืองที่มีกำลังทหารน้อยที่สุดในรอบวันที่แล้วเป็นจุด เริ่ม)
  3. เราจะยึดเมืองได้เมื่อทหารที่เหลือของเรา มากกว่า ทหารของเมืองที่จะไปบุกเท่านั้น! ถ้ามีกำลังเท่านั้นหรือว่าน้อยกว่าถือว่าบุกไม่สำเร็จ
  4. ในการบุกแต่ละครั้ง จะบุกจากเมืองที่มีกำลังรบต่ำที่สุดก่อน แล้วไล่ขึ้นไปเรื่องๆ
  5. ยิ่งเมืองอยู่ไกลขึ้นก็บุกยากขึ้น เพราะถือว่าทหารเราเหนื่อยแล้ว โดยจะถือว่าในวันที่สอง กำลังทหารของเมืองที่จะไปบุกยึดจะ "คูณ2" ในวันที่สามจะ "คูณ3" เพิ่มขึ้นตามวัน
  6. เมืองยึดเมืองได้ กำลังทหารของเราจะลดลงไปเท่ากับเงื่อนไขในข้อที่ผ่านมา แล้วในวันถัดไปเราก็จะใช้กำลังทหารที่เหลือบุกต่อแบบนี้ไปเรื่อยๆ

ขงเบ้งรู้มาว่าคุณเป็นโปรแกรมเมอร์จึงอยากจะใช้ช่วยเขียนโปรแกรม วิเคราะห์ให้ทีว่าด้วยข้อมูลพวกนี้ ถ้าขงเบ้งให้ทหารคุณจำนวน 100 นายเป็นค่าตั้งต้น คุณจะบุกยึดได้กี่เมือง และลำดับของการบุกแต่ละวันมีเมืองอะไรบ้าง

ซึ่งหน้าที่ของเราคือเขียนโปรแกรมซึ่งรายงานผลการรบล่วงหน้าแบบนี้

used: 79
 #1: E D B
 #2: F C
 #3: I
 Result: NO 

ตัวอย่าง

เผื่อไม่เข้าใจสิ่งที่ขงเบ้งต้องการจะสั่งการ เราเลยมี case scenario ตัวอย่างให้ดูสักเล็กน้อย

ใน วันที่ 1 - เราบุกยึดเมือง E D B ตามลำดับ (ไล่จากเมืองทหารน้อยไปมาก) ซึ่งกำลังทหารที่เสียไปจะเท่ากัน 5 + 14 + 20 = 39 ดังนั้นในวันแรกเราจะบุกได้ 3 เมือง และเหลือกำลังทหาร 61 เอาไว้บุกเมืองอื่นๆ ในวันถัดไป
ใน วันที่ 2 - เราจะใช้เมือง E D B ที่บึดได้เมื่อวานเป็นฐานทัพใหม่ในวันนี้ โดยเริ่มจากเมือง E เพราะเป็นเมืองที่มีกำลังทหารน้อยที่สุดซึ่งจะบุดไปที่เมือง F แต่เมื่่อเป็นวันที่สองทำให้เราจะต้องใช้กำลังทหารถึง 16 ในการบุก (แต่ก็ยังบุกได้) ตามด้วยเมือง D ซึ่งเชื่อมต่อกับ 3 เมืองคือ C F H แต่เมือง C และ F เราบุกไปเรียบร้อยซะแล้วเลยเหลือแค่เมือง H .. ในกรณีนี้ไม่สามารถบุกได้เพราะกำลังทหารของเมือง H มีมากเกินไปทำให้การบุกไม่สำเร็จ ซึ่งเป็นเช่นเดียวกันกับการบุกเมือง K
ใน วันที่ 3 - วันที่แล้วบุกเมือง C F มาได้เลยใช้เป็นฐานในการบุกวันนี้ โดยเริ่มจากเมือง C ซึ่งสามารถไปบุกเมือง I D ได้ เราก็จัดการบุกซะ เริ่มจากเมือง I ซึ่งกำลังทหารของเราเพียงพอ แต่ด้านเมือง F ที่ไปบุกเมือง G นั่นมีไม่พอ
วันที่ 4 - เมื่อวานบุกไปได้แค่เมืองเดียวคือ I และตอนนี้เราเหลือทหารแค่ 21 ทำให้บุกเมือง H J ไม่ได้แล้ว

เมื่อ มาถึงขั้นนี้แสดงว่าเราไม่สามารถบุกต่อได้แล้วเพราะกำลังทหารไม่เพียงพอผลก็ คือเราบุกเมือง B C D E F I ได้โดยใช้กำลังทหารไป 79 ไม่สามารถยึดครองทุกเมืองได้

มาเขียนโค้ดกันเถอะ

ก่อนอื่นเลยเราลองมาไล่ดูว่าเราควรจะสร้างอะไรบ้างสำหรับการแก้โจทย์ปัญหานี้

เมืองแต่ละเมืองจะต้องมีการเก็บค่ากำลังทหารของเมืองไว้ และมีการเก็บข้อมูลด้วยว่าเมืองที่เชื่อมต่อกับมันมีเมืองไหนบ้าง

 เมือง (Territory)

สังเกตดูว่าเมืองนั้นมีหลายเมือง และแต่ละเมืองมีคุณสมบัติที่เหมือนกัน ดังนั้นเราก็จะสร้างคลาสเมืองขึ้นมาเพื่อเป็นต้นแบบให้เมืองทั้งหมด

class Territory {

   String name;
   int power = 0;
   ArrayList<Territory> nearby = new ArrayList<Territory>();

   public Territory(String n, int p) {
       name = n.trim();
       power = Math.max(p, 0);
   }
}

สร้าง คลาส Territory ขึ้นมาสำหรับเป็นตัวแทนเมือง ... อย่างที่บอกไปข้างต้น เมืองจำเป็นต้องรู้ข้อมูลคือ name, power และ nearby ก็ใส่เข้าไป พร้อมกับ constructure 1 ตัวให้ด้วย

*เรากำหนดให้ nearby มีชนิดข้อมูลเป็น ArrayList ซึ่ง เก็บ object ของ Territory เพราะเมืองแต่ละเมืองนั้นมีเมืองที่เชื่อมต่อกับมันเยอะ ... ส่วนเหตุผลว่าทำไมไม่ใช้ array แบบธรรมดาก็เพราะว่า array ในภาษา Java ต้องกำหนดขนาดที่ตายตัว เพิ่มลดยืดหดไม่ได้เลย จริงเปลีี่ยนไปใช้ ArrayList แทน

ต่อไปคือเราต้องมาคิดว่าคลาส Territory นี้ทำอะไรได้บ้าง

public class Territory {

    String name;
    int power = 0;
    ArrayList<Territory> nearby = new ArrayList<Territory>();

    public Territory(String n, int p) {
        name = n.trim();
        power = Math.max(p, 0);
    }

    public void addNearby(Territory star) {
        if (!nearby.contains(star)) {
            nearby.add(star);
        }
    }

    public Territory[] getNearby() {
        return Helper.toArray(nearby);
    }
}

สร้าง addNearby กับ getNearby ขึ้นมาเพื่อทำให้เราเซ็ตค่าได้ว่าเมืองนี้จะมีเมืองที่ติดกับมันเป็นอะไรบ้าง

สำหรับ การเซ็ต addNearby นั้นเราก็จะ add มันใส่ลงไปใน ArrayList ที่สร้างไว้ก่อนหน้านี้ และมีการเช็กนิดหน่อยว่าถ้าเราเคยเซ็ตเมืองนี้ไปแล้วก็จะไม่ add เพิ่มอีกด้วย .contain (ประมาณว่าถ้ามัน contain เมืองนี้อยู่ใน ArrayList แล้วก็ไม่จำเป็นจะต้อง add ใส่ลงไปใหม่)

ส่วนการ getNearby นั้นออกแบบให้มัน return กลับมาเป็น "เมืองหลายๆ เมือง" หรือ array ของ Territory .. แต่ว่า nearby เราเก็บข้อมูลเป็นแบบ ArrayList ดันนั้นถ้าจะให้มัน return เป็น array ก็จำเป็นต้องแปลงมันเป็น array แบบธรรมดาเสียก่อนนะ

ป.ล.โดยการแปลนั้นเราใช้คลาส Helper เป็นตัวช่วยในการแปลง (เป็นคลาสที่เขียนขึ้นมาเองใช้สำหรับเป็นฟังก์ชั่นอำนวยความสะดวกเล็กๆ น้อยๆ)

แผนที่ดินแดน (Maps)

เมืองๆ เดียว (มีแค่ Territory) ไม่สามารถแก้โจทย์เราได้เพราะเราต้องสร้างเมืองขึ้นมาหลายเมือง ขั้นต่อไปคือการสร้าง "แผนที่ดินแดน" ขึ้นมา แล้วออกแบบให้คลาสแผนที่ดินแดนนี้สามารถเก็บเมืองได้หลายเมืองตามที่เราต้อง การ

class Maps {

    Territory[] territories = null;
    Territory start;

    public Maps(int numberOfTerritory) {
        territories = new Territory[numberOfTerritory];
   }
}

ก็มาดูกันว่า Maps ของเราต้องมีอะไรบ้าง

อย่างแรกที่แผนที่ดินแดนจะต้องบันทึกเก็บไว้ก็คือ "ดินแดนนี้มีเมืองอะไรบ้าง" และ เมืองที่อยู่ของขงเบ้งคือเมืองไหน

class Maps {

    Territory[] territories = null;
    Territory start;

    public Maps(int numberOfTerritory) {
        territories = new Territory[numberOfTerritory];
    }

    void setTerritory(int idx, String name, int mana) {
        if (idx >= 0 && idx < territories.length) {
            territories[idx] = new Territory(name, mana);
        }
    }

    Territory getTerritory(String name) {
        for (Territory checkpoint : territories) {
            if (checkpoint.name.equals(name.trim())) {
                return checkpoint;
            }
        }
        return null;
    }

    void setStartPoint(String name) {
       start = getTerritory(name);
    }
 
    Territory getStartPoint() {
        return start;
    }
}

ตาม หลักการออกแบบคลาส ในเมื่อ Maps นั้นเก็บ Territory หลายๆ ตัว ดังนั้นควรจะมี method สำหรับ set และ get เจ้า Territory เอาไว้ ... แต่ Maps ของเรามี start ซึ่งเป็นเมืองจุดเริ่มด้วยกับเขียนเพิ่มเข้าไป

** การเขียน method สำหรับเซ็ตค่าและขอค่าในคลาสแบบนี้มีชื่อเรียกว่า getter และ setter ซึ่งถือเป็น method แบบง่ายที่สุดเวลาเขียน OOP ไว้มีเวลาจะมาเขียนเรื่องหลักการออกแบบคลาสทีหลังอีกทีละกัน

แต่ ถ้าเรามี "เมือง" และ "แผนที่ดินแดน" ซึ่งเก็บเมืองหลายๆ เมืองอย่างเดียวก็คงไม่มีประโยชน์อะไร ในเมืองไม่รู้ว่าบุกเมืองนี้แล้วจะไปเมืองไหนต่อได้ เราจึงจะเพิ่ม method สำหรับเซ็ตค่าว่าเมืองไหนเชื่อมกันบ้างอีก

void setNearby(String name1, String name2) {
 Territory t1 = getTerritory(name1);
 Territory t2 = getTerritory(name2);
 t1.addNearby(t2);
 t2.addNearby(t1);
}

method แบบง่ายๆ ซึ่งทำหน้าที่แค่รับชื่อเมืองมา 2 เมือง แล้วเซ็ตค่าบอก Territory ทั้งสองตัวนั้น (คือ Territory t1 และ t2 ในโค้ดตัวอย่าง) แล้วมันก็ไม่ต้องทำไรมากนอกจากไปเรียกใช้ .addNearby ซึ่งเป็น method ของ Territory ที่เราเขียนไปแล้วตั้งแต่ต้นให้ทำงานก็เท่านั้น

บอกว่า t1 เชื่อมไปหา t2 ได้ และ t2 สามารถเชื่อมไปหา t1 ได้ = ทั้งสองเมืองมันเชื่อมกันแล้วนั่นเอง

เซ็ตค่า (main)

เมื่อมี แผนที่ดินแดน เรียบร้อย อย่างต่อไปที่ต้องทำคือการเซ็ตค่าเริ่มต้นให้แผนที่ตัวนี้

public static void main(String[] args) {

Maps land = new Maps(cmdStars.length);
 land.setTerritory(0, "A", 100);
 land.setTerritory(0, "B", 20);
 land.setTerritory(0, "C", 3);
 land.setTerritory(0, "D", 14);
 land.setTerritory(0, "E", 5);
 land.setTerritory(0, "F", 8);
 land.setTerritory(0, "G", 18);
 land.setTerritory(0, "H", 21);
 land.setTerritory(0, "I", 6);
 land.setTerritory(0, "J", 7);
 land.setTerritory(0, "K", 25);
 land.setTerritory(0, "L", 4);
 land.setNearby("A", "B");
 land.setNearby("A", "D");
 land.setNearby("A", "E");
 land.setNearby("B", "C");
 land.setNearby("B", "K");
 land.setNearby("C", "D");
 land.setNearby("C", "I");
 land.setNearby("D", "F");
 land.setNearby("D", "H");
 land.setNearby("E", "F");
 land.setNearby("F", "G");
 land.setNearby("H", "J");
 land.setNearby("H", "I");
 land.setNearby("I", "J");
 land.setNearby("K", "L");
}

สร้าง object จากคลาส Maps ให้ชื่อว่า "land"

แล้วก็เซ็ตค่าลงไปตรงๆ เลย เท่านี้เป็นอันเสร็จ เราก็จะได้ดินแดนที่มีเมืองพร้อมกำลังทหารแต่ละเมืองพร้อมใช้งาน >__<

ป.ล.ตาม โจทย์จริงๆ จะใช้เป็นการอ่านไฟล์แทน แต่เนื่องจากการอ่านไฟล์เขียนไปหลายครั้งแล้วในโปรเจคก่อนหน้านี้จึงขอข้าม ไป เนื่องจากแค่อ่านไฟล์มา แล้วส่วนเซ็จค่าพวกนี้ใช้ loop แทนก็เสร็จแล้ว ง่ายๆ

เตรียมพร้อมสำหรับการบุกเมืองที่อยู่ใกล้เคียง

เมื่อเราเตรียมข้อมูล ทุกอย่างพร้อมแล้ว (คือมีเมือง และเซ็ตค่าว่าเมืองนี้มีกำลังทหารเท่าไหร่และเชื่อมต่อกับเมืองไหนอีกบ้าง) เราก็จะเริ่มส่งทหารออกไป!

Territory start = land.getTerritory("A");
int initPower = start.power;

เริ่มบุกจากเมือง A ของขงเบ้ง ก็เตรียมข้อมูลเริ่มต้นให้เรียบร้อย โดย startแทนเมืองเริ่มต้น และ initPower คือค่ากำลังทหารเริ่มต้นของเมืองนั้น


แต่เวลาเราบุกเมืองพวกนี้ต้องมีตัวบันทึกว่าเมืองนี้เราเคยผ่านไปรึยัง เพราะถ้าเคยผ่านไปแล้วเราจะไม่บุกมันซ้ำ

ArrayList<Territory> pass = new ArrayList<Territory>();

แต่ เราต้องการจะเก็บแผนการด้วยว่าวันนึงๆ เนี่ยบุกเมืองไหนไปแล้วได้บ้างก็ต้องสร้างตัวเก็บข้อมูลตัวนี้ขึ้นมาอีกตัว โดยเราไม่รู้ว่าจะมีทั้งหมดกี่วัน และในวันหนึ่งๆ นั้นมีลิสต์ของเมืองที่บุกไปเป็นอะไรบ้าง?

ArrayList<Territory[]> plans = new ArrayList<Territory[]>();

ใช้ ArrayList เก็บ Territory[] ซึ่งคือลิสต์ของเมืองที่บุกในหนึ่งวัน

int currentPower = initPower, day = 1;
boolean all = true;

pass.add(start);
Territory[] nextTargets = start.getNearby();
Arrays.sort(nextTargets);

ArrayList<Territory> conquered;

เตรียม ตัวแปรสำหรับนับว่าตอนนี้เราเหลือกำลังทหารเท่าไหร่กัน และวันนี้เป็นวันที่เท่าไหรในการบุก (ต้องรูปวันเพราะวันที่ 2 3 4 ... ต่อๆ ไป กำลังทหารของเมืองอื่นๆ จะแข็งแรงขึ้น)

ส่วนตัวแปร all เอาไว้เช็กว่าเราบุกได้ครบทุกเมืองรึเปล่า

เป้าหมายชุดแรกของเราก็มาจาก nextTargets ซึ่งเป็น เมืองที่อยู่ติดกันกับ start แต่ตามกฎบอกไว้ ว่าเราจะบุกจากเมืองที่มีกำลังทหารน้อยที่สุดซะก่อน เราจึงเรียกใช้ Arrays.sort(); ซึ่งเป็นสิ่งที่ Java มีไว้ให้ใช้อยู่แล้วสำหรับการเรียงข้อมูล

สำหรับ conquered ตัวล่าสุดนั้นสร้างมาสำหรับเก็บว่าในวันหนึ่งเราบุกยึดเมืองไหนไปแล้วบ้าง (ในวันนี้วันเดียว ไม่เอาวันที่แล้วนะ)

แต่ทว่า... 

การที่เราจะเรียกใช้ Arrays.sort ได้นั้น จะต้องเป็นสิ่งที่ Java รู้ว่าจะเรียงลำดับข้อมูลยังไง เช่น int หรือ String เป็นต้น

แต่คลาส Territory เป็นคลาสที่เราสร้างเอง Javaไม่รู้แน่นอน (มันโง่) ว่าวิธีการเปรียบเทียบเมืองจะต้องทำอย่างไร

อินเตอร์เฟส Comparable

วิธีแก้คือ สอนให้ Java มันรู้ว่าคลาสของเรามีวิธี "เปรียบเทียบ" กันอย่างไรโดยใช้ อินเตอร์เฟสที่ชื่อว่า Comparable

class Territory implements Comparable<Territory> {
...
    @Override
    public int compareTo(Territory other) {
        return power - other.power;
    }
}

คลาสที่มีความสามารถ comparable ได้จะต้องมีเมดทอดที่ชื่อว่า compareTo เอาไว้สอน Java ว่าคลาสของเราเปรียบเทียบว่าตัวไหนมากกว่า ตัวไหนน้อยกว่ายังไง

ซึ่งคลาส Territory นั้นดูว่าตัวไหนมีค่ามากกว่ากันก็ดูที่ตัวแปร power นั่นเอง

เริ่มบุก (invade)

เงื่อนไข ของการบุกไม่มีอะไรมาก ก็ตามเงื่อนไขที่พูดไปแล้วข้างบน โดยจะหยุดก็ต่อเมื่อ "ในวันที่ผ่านมา ไม่มีเมืองที่บุกได้เพิ่มแล้ว" ... ประโยคนี้แปลความได้ 2 อย่างคือหยุดการบุกเพราะบุกครบทุกเมืองแล้ว เลยไม่เหลือเมืองให้บุกอีก และอีกอย่างคือ กำลังทหารมีไม่พอสำหรับการบุกเมืองที่เหลือแล้วนั้นเอง


เราจะบุกเมืองที่อยู่ในลิสต์ของ nextTarget (มันเป็น array มีหลายเมืองเก็บอยู่ จะบุกทุกเมืองเลยใช้ loop วนเอาไงล่ะ)

for (Territory target : nextTargets) {
    //วนลูปแบบ for each จะได้ว่าในรอบนึงเราจะบุกเมือง target

    if (pass.contains(target)) {
       continue;
    }

    int mp = target.power * day;
    if (mp >= currentPower) {
        all = false;
        continue;
    }

    //ถ้าเลยมาถึงตรงนี้แปลว่าบุกได้ไงล่ะ >_<
}

แต่ก่อนจะบุกเมืองเป้าหมายได้ เราต้องเช็ก 2 สเต็ปคือ

  1. เมืองนั้นเคยผ่านมาหรือยัง?
  2. มีกำลังทหารเพียงพอที่จะบุกหรือไม่?

* คลาส ArrayList นั้นสามารถเช็กได้ว่าข้อมูลตัวนี้ๆๆ อยู่ใน ArrayList แล้วหรือยังโดยการใช้คำสั่ง .contains() แต่ต้องใช้คู่กับ...

class Territory implements Comparable<Territory> {
...
    @Override
    public boolean equals(Object other) {
        return other == null ? false : this.name.equals(((Territory) other).name.trim());
    }
}

คำ สั่ง .equals นั้นเป็นคำสั่งพื้นฐานมากๆๆๆ ของ Java มันก็จะมาเรียกใช้คำสั่งนี้แหละ ดังนั้นคลาส Territory นอกจาก .compareTo ที่สร้างไปเมื่อกี้ก็ต้องสร้าง .equals เข้าไปด้วย

ครั้งที่แล้วเอามา เปรียบเทียบกันทำด้วยค่า power พอจะเปรียบเทียบกันว่ามันเป็นเมืองเดียวกันหรือเปล่า ก็จะเทียบด้วยค่า name หรือชื่อเมืองนั่นเอง

conquered.add(target);
currentPower -= mp;
pass.add(target); 

เมื่อเราบุกเมืองได้ก็มีสิ่งที่เราจะต้องทำคือ เพิ่มเมืองนี้เราไปในรายการ conquered ว่าเราบุกเมือง target นี้ไปนะๆ เมื่อบุกเสร็จนั่นหมายความว่ากำลังทหารของเราจะลดไปด้วย

ตบท้ายด้วยการบอกว่าเมืองเป้าหมายนี่น่ะ มัน pass ไปแล้วนะ จะได้ไม่มีการบุกเมืองนี้ซ้ำ 2 รอบ

ตามแผนการศึก (ฮา) เราบอกว่าเมืองไหนที่เราบุกยึดได้ในรอบวันนี้ เราจะใช้เป็นฐานเมืองบุกเมืองต่อไปในวันพรุ่งนี้

นั่น หมายความว่าเมืองไหนก็ตามที่เชื่อมต่อกับเมืองที่เรา conquered ไปแล้วในวันนี้จะกลายเป็น nextTarget ของเราในรอบวันหน้าต่อไป ดังนั้นก่อนจะจบเราจึงต้องอัพเดตค่า nextTarget ซะก่อน

nextTargets = null;
if (!conquered.isEmpty()) {
    plans.add(Helper.toArray(conquered));
    for (Territory newBase : conquered) {
        Territory[] nextAdjacent = newBase.getNearby();
        Arrays.sort(nextAdjacent);
        nextTargets = Helper.concat(nextTargets, nextAdjacent);
   }
}

วิธีการอัพเดตก็ไม่มีอะไรมาก นั่นคือดูว่าครั้งที่แล้วมีเมืองไหนบ้างที่เรา conquered ไปแล้ว ก็เอาเมืองพวกนั้นมาวนลูปแล้วดูว่ามันมีเมืองข้างเคียงเป็นเมืองอะไรบ้าง จากนั้นก็ทำการ sort เพื่อให้เมืองพวกนั้นเรียงลำดับจาก power น้อยไปมาก แล้วเก็บลงตัวแปร nextTargets  เพื่อเอาไว้ใช้เป็นตัวตั้งต้นรอบวันต่อไป

while ( nextTargets != null ) {
    conquered = new ArrayList<Territory>();
    //โค้ดที่เราเรียนไปเมื่อกี้สดๆ ร้อนๆ ข้างบน
    day++;
}

เพราะ เราไม่รู้ว่าเราจะต้องใช้กี่วันในการบุกเลยเอาทั้งหมดที่เขียนเมืองกี้ ครอบด้วย while loop และใช้เงื่อนไขว่า nextTargets ยังมีอยู่ (ไม่เท่ากับ null)

ทีนี้ก็จบ!

เราตัวแปรที่เก็บค่าคำตอบมาปริ๊นก็จะได้ output ที่ต้องการ

System.out.println("===============================");
System.out.println("Start: " + start);
System.out.println("Mana used: " + (initPower - currentPower));

day = 1;
for (Territory[] plan : plans) {
    System.out.print("#" + (day++) + ": ");
    for (Territory star : plan) {
        System.out.print(star.name + " ");
    }
    System.out.println();
}

System.out.println("Conclusion: " + (all ? "YES" : "NO"));

เหมือนะยากเนอะ แต่ถ้าเข้าใจหลักการค่อยๆ คิด เขียนไปเรื่อยๆ ก็จะได้คำตอบเองแหละนะ

534 Total Views 3 Views Today
Ta

Ta

สิ่งมีชีวิตตัวอ้วนๆ กลมๆ เคลื่อนที่ไปไหนโดยการกลิ้ง .. ถนัดการดำรงชีวิตโดยไม่โดนแสงแดด
ปัจจุบันเป็น Senior Software Engineer อยู่ที่ Centrillion Technology
งานอดิเรกคือ เขียนโปรแกรม อ่านหนังสือ เขียนบทความ วาดรูป และ เล่นแบดมินตัน

You may also like...

ใส่ความเห็น

อีเมลของคุณจะไม่แสดงให้คนอื่นเห็น ช่องที่ต้องการถูกทำเครื่องหมาย *