프로그래머스 : 여행경로

코딩테스트 연습 - 여행경로

 

 

조건 1. 모든 도시를 거친다.
조건 2. 티켓을 다 쓴다. (answer.length == tickets.length + 1)

 

이 문제는 깊이탐색으로 풀 수 있는 문제다. 깊이탐색의 개념에 대해서 잘 모르면, 왜 깊이탐색을 써야하는지 이해가 안갈 수 있다. 

 

그래프의 탐색방법은 기본적으로 너비탐색과 깊이탐색이있다. 너비탐색은 마치 개미굴에 물을 붓듯이 처음부터 모든 경우의 수를 탐색하므로 이 문제에는 적절치 않다.

그보다는 깊이탐색처럼 한 깊이로 끝까지 갔다가, 막다른 길이면 분기점까지 되돌아오는 방식을 쓰는게 좋다.

깊이탐색을 이용할때 쓰는 스택은 분기(자식노드로 갈라짐)를 기억하고 있기 때문에 가능하다.

 

깊이탐색을 할때는 자료구조인 스택을 이용해도 되고, 재귀함수를 이용해도 된다. (재귀함수를 이용하면 함수호출자체가 스택구조로 이루어지기 때문에 가능하다)

 

이 문제같은 경우에는 재귀함수를 이용하는게 더 편하다. 왜냐하면 경로를 출력해야하기 때문이다. 

자료구조 스택을 이용했을때는 막다른길(리프노드)이 나왔을때, 전에 기억해둔 분기로 점프하듯 되돌아간다.

재귀함수는 리프노드에서 분기까지 호출스택에서 함수를 하나하나 풀면서 되돌아간다. 

 

 

그림판 극혐

 

 

그렇기 때문에 최종결과로 경로를 출력하는거라면 재귀쪽이 좀더 편하다.

만약 의도치 않은 경로였다면 되돌아가면서 경로를 수정할 수 있으니까.

 

그럼이제 코드를 보자.

 

  public boolean dfs(String start, String[][] tickets, ArrayList<Boolean> checked, ArrayList<String> answer, int endSize, int count)
    {
        //일단 경로에 넣자.
        answer.add(start);

        //만약 모든 티켓을 사용했다면
        if(answer.size() >= endSize +1)
            return true;

        for(int i = 0; i<tickets.length; ++i) {

            //start와 티켓의 출발지가 같고, 사용하지 않은 티켓이면
            if(tickets[i][0].equals(start) && !checked.get(i))
            {
                //사용했다고 표시
                checked.set(i, true);
                //자식노드로 하여금 현재 사용한 티켓의 목적지를 출발지로 하는 티켓을 찾아서 똑같은 로직을 반복하도록 한다.
                boolean result = dfs(tickets[i][1], tickets, checked, answer, endSize,count +1);

                //만약 if(answer.size() >= endSize +1)에 결려서 true를 리턴했다면 끝
                if(result)
                    return true;
                //아니면 현재 사용한 티켓을 사용하지 않은 상태로 만든다. (무른다)
                else
                    checked.set(i, false);

            }

        }

        //만약 모든티켓을 사용하지 않았다면
        answer.remove(answer.size() - 1);
        return false;


    }


    public String[] solution(String[][] tickets) {

        Arrays.sort(tickets, (a, b) -> {
            String Astr = a[0] + a[1];
            String Bstr = b[0] + b[1];
            return Astr.compareTo(Bstr);
        });



        //리스트 초기화와 동시에 배열방 확보
        ArrayList<Boolean> checked = new ArrayList<Boolean>(Arrays.asList(new Boolean[tickets.length]));
        Collections.fill(checked, false);



        String[] answer = {};
        ArrayList<String> path = new ArrayList<>();
        dfs("ICN", tickets, checked, path, tickets.length, 0);
        return path.toArray(answer);
    }

 

 

dfs 함수의 원리는 간단하다.

먼저 for문을 보자.

for문에서는 티켓을 순회하면서 현재 인자로 들어온 start와 출발지가 일치하는 티켓을 찾고있다.

만약 찾았으면 사용하고, 사용한 티켓의 목적지가 출발지인 티켓을 찾는다.

(자식노드에게 찾도록 한다고 주석에는 써놨지만, 엄밀히 말하면 그래프와 같은 구조이므로 자식이 아니라 인접노드이다)

만약 티켓을 모두 사용했다면 true를 반환해서 호출자에게 던져주고, 호출자는 true를 받으면 그대로 위로 던진다.

만약 티켓을 모두 사용하지 않았는데 함수가 끝났다면 호출자에게 false를 던져주고, 호출자는 사용했던 티켓을 무른다.

 

이와같은 재귀함수가 끝나고 answer에 담긴 경로가 답이다.