Table of contents

프로그래머스 여행경로

[출발 공항, 목적지 공항]로 이루어진 이차원 배열의 항공권 목록이 주어졌을 때, "ICN" 공항에서 출발하여 모든 티켓을 사용할 수 있는 경로를 구하는 문제이다.

이번에도 dfs를 사용했다. 프로그래머스 고득점 kit에 있는 dfs 문제에는 경로, 단계, 최소, 최대, 연산자라는 단어가 자주 등장하는 것 같다. boolean배열, 재귀, 백트래킹이 떠오른다면 dfs 문제라고 봐도 될 것 같다.

@Test
public void testTravelPath() {
    assertThat(travelPath("ICN", new String[][] {
        {"ICN", "JFK"},
        {"HND", "IAD"},
        {"JFK", "HND"},
    })).isEqualTo(new String[] {
        "ICN", "JFK", "HND", "IAD"
    });

    assertThat(travelPath("ICN", new String[][] {
        {"ICN", "JFK"},
        {"HND", "IAD"},
        {"JFK", "HND"},
    })).isEqualTo(new String[] {
        "ICN", "JFK", "HND", "IAD"
    });

    assertThat(travelPath("1", new String[][] {
        {"1", "2"},
        {"1", "3"},
        {"3", "1"}
    })).isEqualTo(new String[] {
        "1", "3", "1", "2"
    });
}


boolean[] used;
private String[] travelPath(String from, String[][] tickets) {
    used = new boolean[tickets.length];
    Deque<String> result = new ArrayDeque<>();
    Arrays.sort(tickets, Comparator.comparing((String[] o) -> o[1]));
    dfs(tickets, result, from, 0);
    return result.toArray(new String[result.size()]);
}

private boolean dfs(String[][] tickets, Deque<String> result, String from, int count) {
    result.addLast(from);

    if (count == tickets.length) {
        return true;
    }

    for (int i = 0; i < tickets.length; i++) {
        if (tickets[i][0].equals(from) && !used[i]) {
            used[i] = true;
            boolean success = dfs(tickets, result, tickets[i][1], count + 1);
            if (success) return true;
            used[i] = false;
        }
    }

    result.removeLast();
    return false;
}

boolean 배열 + dfs를 이용한 코드이다.

@Test
    public void testTravelPath() {
        TravelPath travelPath = new TravelPath(new String[][] {
                {"ICN", "JFK"},
                {"HND", "IAD"},
                {"JFK", "HND"}});
        assertThat(travelPath.path("ICN")).isEqualTo(new String[] {
                "ICN", "JFK", "HND", "IAD"
        });
        
        travelPath = new TravelPath(new String[][] {
                {"ICN", "SFO"},
                {"ICN", "ATL"},
                {"SFO", "ATL"},
                {"ATL", "ICN"},
                {"ATL", "SFO"}});
        assertThat(travelPath.path("ICN")).isEqualTo(new String[] {
                "ICN", "ATL", "ICN", "SFO", "ATL", "SFO"
        });
        
        travelPath = new TravelPath(new String[][] {
                {"1", "2"},
                {"1", "3"},
                {"3", "1"}
        }));
        assertThat(travelPath.path("ICN")).isEqualTo(new String[] {
                "1", "3", "1", "2"
        });
    }

class TravelPath {
    Ticket[] tickets;

    class Ticket {
        String from;
        String to;
        boolean used;

        public Ticket(String from, String to) {
            this.from = from;
            this.to = to;
        }
    }

    public TravelPath(String[][] tickets) {
        this.tickets = new Ticket[tickets.length];
        for (int i = 0; i < tickets.length; i++) {
            this.tickets[i] = new Ticket(tickets[i][0], tickets[i][1]);
        }
        Arrays.sort(this.tickets, Comparator.comparing(o -> o.to));
    }

    public String[] path(String from) {
        Deque<String> result = new ArrayDeque<>();
        dfs(from, result, 0);
        return result.toArray(new String[result.size()]);
    }

    private boolean dfs(String from, Deque<String> result, int count) {
        result.addLast(from);

        if (count == tickets.length) {
            return true;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!tickets[i].used && tickets[i].from.equals(from)) {
                tickets[i].used = true;
                boolean success = dfs(tickets[i].to, result, count + 1);
                if (success) {
                    return true;
                }
                tickets[i].used = false;
            }
        }


        result.removeLast();
        return false;
    }
}

위의 코드는 boolean 배열을 사용하지 않고 Ticket 클래스 자체에 넣어서 사용한다.

딱히 어려운 문제는 아니니 설명이 필요없지만, 주의해야할 부분이 하나 있다. [["1", "2"], ["1", "3"], ["3", "1"]] 을 예로 살펴보자. "1"부터 시작한다고 가정한다.

2와 3 사이에는 경로가 없다. 2가 사전순으로 먼저 등장하기 때문에 2를 먼저 탐색하게 되는데, 2에서 갈 수 있는 경로가 없으므로 이전 경로로 돌아가야한다. 이 부분을 감안하지 않고 코드를 작성하다보면 1, 2 케이스가 실패한다. dfs에서는 주로 방문한 노드를 체크하고, 돌아올 때 체크를 해제한다. Ex) tickets[i].used = true; ......... tickets[i].used = false;

여기서는 그런 방법과 비슷하게, 모든 티켓을 사용하지 않았음에도 다음으로 이어지는 경로가 없다면 경로를 삭제하고 다시 이전 스택으로 돌아가서 티켓의 상태를 되돌린 후, 다음 티켓부터 다시 탐색한다.