Today's Algorithm(2018-11-22)

programmers 여행경로

어제 짧은 시간이었지만 문제를 풀었는데 테스트케이스 4개 중에 2개가 '런타임오류'가 발생하였습니다. 뭐가 무엇인지 찾지 못하다가 같이 스터디하는 멤버로부터 받은 커스텀 테스트케이스를 돌려봄으로써 어떤 것에서 오류가 발생했는지 알았네요. 그럼 저는 문제를 어떻게 해결했는지 간략하게 정리해볼께요.

 

1. 먼저 티켓들을 원하는대로 쉽게 꺼내기 위해 자료구조를 만들건데요. 우선 이전에 Ticket이라는 클래스를 만들었습니다. (출발지, 도착지, 사용여부) 이렇게 3개의 상태값을 가지고 있습니다.

class Ticket implements Comparable<Ticket> {
    String departure;
    String arrival;
    boolean used;

    public Ticket(String departure, String arrival, boolean used) {
        this.departure = departure;
        this.arrival = arrival;
        this.used = used;
    }

    @Override
    public int compareTo(Ticket o) {
        return this.arrival.compareTo(o.arrival);
    }
}

​ 여기서 compareTo 를 오버라이딩한 이유는 도착지를 알파벳 순서대로 정렬하기 위함입니다. 문제의 조건에서 여러가지 경로가 존재할 때 알파벳 순서대로 가장 빠른 것이 정답이거든요.

2. Tikect을 만들었으면 이를 담을 것이 필요하겠죠. 전 출발지를 기준으로 꺼내기 쉽도록 Map을 만들었는데요. Value값에 List를 넣었어요. 도착지가 다른 경우의 티켓도 존재할 수 있으니까요. 그래서 Map<String, List<Ticket>> 와 같이 만들었습니다.

3. 자! 이렇게 입력값들을 꺼내기 쉽게 재구성했다면 이젠 그것을 이용하여 문제 핵심로직 dfs함수를 만들어야 합니다. dfs 안 내용을 풀어쓰면 다음과 같습니다.

   • map에서 해당 키값(출발지)의 value값(도착지 List)를 foreach문을 돌립니다. 그럼 해당 티켓(들)이 존재하겠죠?
   • 우선 종료조건으로 이전에 방문한 도시의 수가 마지막 도시를 제외한 수랑 일치할 때 return을 시킵니다.
   • 종료조건이 아니라면 도착지 중 방문하지 않은 곳을 찾습니다. 만약 있다면 그곳을 Stack에 넣어두고 방문 표시합니다. 그리고 다시 도착지를 출발점으로 하여 dfs를 돌립니다.(방문한 곳을 다시 방문 가능하게 되면 무한반복이 발생할 수 있습니다. Stack에 넣는 이유는 제일 마지막 여행지를 넣고 빼기가 가장 수월하기 때문입니다)
   • dfs함수 이후엔 backtracking을 위해 Stack에 넣어두었던 도시를 빼내고 방문 표시를 다시 안함으로 표시합니다.(dfs를 통해 해당 경우의 수를 모두 고려했는데 종료조건이 충족되지 않았으니 그 도시를 아니라는 것이고 다음 경우의 수를 위해 방문표시도 돌려놓는 것이죠!)

4. 마지막으로 Stack에 담긴 도시들을 뒤에서부터 차례대로 배열에 담아 정답으로 제출할 수있도록 합니다.

 

처음엔 위와 같이 짰습니다. 그런데 몇 가지 문제가 생겼습니다.

• 종료조건까진 잘오는데 종료조건까지 오면서 부수적으로 불러진(종료조건까진 오진 못하는) dfs함수가 이후에 Stack에 pop이 되면서 다 만들어진 Stack값들을 빼내는 것입니다. 따라서 종료조건에 도달하면 flag로 따로 표시하여 dfs내에 종료조건이 성립되면 flag를 통해 더이상 정답에 영향을 줄 아무런 처리를 하지 못하게 하였습니다.
• 위 문제를 해결할 줄 알았는데 문제에서 '런타임에러'가 계속 발생하였습니다. 그런데 스터디 멤버가 직접 만든 테스트 케이스를 넣어보면서 dfs돌렸을 때 map에서 해당 출발지에서 도착하는 티켓이 없는 경우를 생각하지 못해 NullPointException이 발생하는 것을 확인하였습니다. 따라서 if (map.containsKey(departure)) 을 통해 도착점 값이 있을 때만 계속 진행되도록 하니 해결할 수 있었습니다.

코드는 다음과 같습니다.

class Solution {
    boolean flag = false;
    public String[] solution(String[][] tickets) {
        Map<String, List<Ticket>> map = init(tickets);
        Stack<String> answer = new Stack<>();
        answer.push("ICN");
        dfs(map, answer, "ICN", 0, tickets.length);
        String[] submit = new String[answer.size()];
        for (int i = answer.size() - 1; i >= 0; i--) {
            submit[i] = answer.pop();
        }
        System.out.println(Arrays.asList(submit));
        return submit;
    }

    void dfs(Map<String, List<Ticket>> map, Stack<String> answer, String departure, int pass, int target) {
        if (map.containsKey(departure)) {
            for (Ticket ticket : map.get(departure)) {
                if (!flag && ticket.used == false) {
                    if (pass == target - 1) {
                        answer.push(ticket.arrival);
                        flag = true;
                        return;
                    }
                    ticket.used = true;
                    answer.push(ticket.arrival);
                    dfs(map, answer, ticket.arrival, pass + 1, target);
                    if (flag) return;
                    ticket.used = false;
                    answer.pop();
                }
            }
        }
    }

    private Map<String, List<Ticket>> init(String[][] tickets) {
        Map<String, List<Ticket>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            if (map.containsKey(ticket[0])) {
                map.get(ticket[0]).add(new Ticket(ticket[0], ticket[1], false));
                continue;
            }
            List<Ticket> tempList = new ArrayList<>();
            tempList.add(new Ticket(ticket[0], ticket[1], false));
            map.put(ticket[0], tempList);
        }
        for (String s : map.keySet()) {
            Collections.sort(map.get(s));
        }
        return map;
    }
}

아쉬운 점은 '굳이 flag를 사용할 필요가 있었는가'입니다. dfs함수를 좀 더 잘 짜고 싶었는데 다른 방법이 잘 생각이 안나더라구요. 좀 더 많은 PS와 다른 사람의 코드를 봄으로써 익혀나가야 할 것 같습니다.

오늘 추가적으로 공부한 부분

• 2018/11/23 - [Algorithm/problem solving] - Today's Algorithm(2018-11-22)