ohj8447   3년 전

질문게시판에 있는 대부분의 반례를 적용해도 문제가 없는데

실행을 하면 16%에서 자꾸 틀립니다. 예외 상황이 있을까요?

현재까지 실행해본 반례로는 아래와 같습니다.

public class SpecificShortestRouteTest {
    @Test
    public void test1() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(2, 3, 3);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(1, 3, 5);
        ssr.addRoute(2, 4, 5);
        ssr.addRoute(1, 4, 6);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(7));
    }

    @Test
    public void test2() {
        int nodeCount= 4;
        int routeCount = 5;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 3, 4);
        ssr.addRoute(1, 4, 6);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(4, 2, 2);
        ssr.addRoute(2, 3, 3);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(11));
    }

    @Test
    public void test3() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 4, 1);
        ssr.addRoute(4, 2, 1);
        ssr.addRoute(2, 3, 1);
        ssr.addRoute(2, 4, 1);
        ssr.addRoute(3, 1, 1);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(5));
    }

    @Test
    public void test4() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 3, 4);
        ssr.addRoute(1, 4, 6);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(2, 3, 3);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(11));
    }

    @Test
    public void test5() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 3, 4);
        ssr.addRoute(1, 4, 6);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(4, 2, 2);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(11));
    }

    @Test
    public void test6() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 3, 4);
        ssr.addRoute(1, 4, 6);
        ssr.addRoute(4, 2, 2);
        ssr.addRoute(2, 3, 3);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(15));
    }

    @Test
    public void test7() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 4, 1);
        ssr.addRoute(4, 2, 1);
        ssr.addRoute(2, 3, 1);
        ssr.addRoute(2, 1, 1);
        ssr.addRoute(3, 2, 1);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(4));
    }

    @Test
    public void test8() {
        int nodeCount= 4;
        int routeCount = 5;
        int[] midRoute = {1,4};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(2, 3, 3);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(1, 3, 5);
        ssr.addRoute(2, 4, 5);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(6));
    }

    @Test
    public void test9() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {1,4};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(2, 3, 3);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(1, 3, 5);
        ssr.addRoute(2, 4, 5);
        ssr.addRoute(1, 4, 4);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(4));
    }

    @Test
    public void test10() {
        int nodeCount= 4;
        int routeCount = 3;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 4, 1);
        ssr.addRoute(2, 4, 2);
        ssr.addRoute(3, 4, 3);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(11));
    }

    @Test
    public void test11() {
        int nodeCount= 4;
        int routeCount = 1;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 4, 6);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(-1));
    }

    @Test
    public void test12() {
        int nodeCount= 4;
        int routeCount = 6;
        int[] midRoute = {1,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(2, 3, 3);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(1, 3, 5);
        ssr.addRoute(2, 4, 5);
        ssr.addRoute(1, 4, 4);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(6));
    }

    @Test
    public void test13() {
        int nodeCount= 5;
        int routeCount = 4;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(2, 5, 3);
        ssr.addRoute(3, 4, 1);
        ssr.addRoute(1, 5, 5);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(-1));
    }

    @Test
    public void test14() {
        int nodeCount= 4;
        int routeCount = 4;
        int[] midRoute = {2,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 1);
        ssr.addRoute(1, 3, 1);
        ssr.addRoute(2, 3, 9);
        ssr.addRoute(2, 4, 9);
        ssr.addRoute(3, 4, 1);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(4));
    }

    @Test
    public void test15() {
        int nodeCount= 3;
        int routeCount = 4;
        int[] midRoute = {1,3};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 1);
        ssr.addRoute(1, 3, 3);
        ssr.addRoute(2, 3, 1);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(2));
    }

    @Test
    public void test16() {
        int nodeCount = 7;
        int routeCount = 7;

        int[] midRoute = {2,6};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.addRoute(1, 2, 3);
        ssr.addRoute(3, 2, 5);
        ssr.addRoute(1, 3, 1);
        ssr.addRoute(6, 5, 3);
        ssr.addRoute(7, 5, 8);
        ssr.addRoute(5, 4, 2);
        ssr.addRoute(6, 4, 3);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(-1));
    }

    @Test
    public void test17() {
        int nodeCount = 800;
        int routeCount = 799;

        int[] midRoute = {1,800};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        for(int i = 1 ; i < nodeCount ; i++) {
            ssr.addRoute(i, i+1,1000);
        }

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(799000));
    }

    @Test
    public void test18() {
        int nodeCount = 800;
        int routeCount = 0;

        int[] midRoute = {1,800};

        SpecificShortestRoute ssr = new SpecificShortestRoute();
        ssr.initialize(nodeCount);

        ssr.setMidRoute(midRoute);
        ssr.run();

        <i>assertThat</i>(ssr.getResult(), <i>is</i>(-1));
    }
}

ohj8447   3년 전

구글 검색으로 원인을 알아냈습니다.

지나야 할 Route가 {M1, M2} 라고 가정할 때

Start -> M1 -> M2 -> End 와 추가로

Start -> M2 -> M1 -> End 와 같이 정방향이 아닌 역방향이 가능합니다.

해당 연산 부분을 추가하니 간단하게 해결됬습니다,

해당 방법을 사용하면 test의 결과가 달라지게 되는데

test2 = 9

test3 = 3

test5 = 9

test5 = 9

의 변경된 결과를 가집니다.

댓글을 작성하려면 로그인해야 합니다.