문제

여행경로

풀이

이 문제는 모든 티켓을 사용하여야 한다 라는 문항이 있다. 처음에 알파벳 순으로 가는 것만 생각해서 정렬을 해주고 난 다음에 이것대로 bfs로 선택하면 되겠구나 라는 생각을 했으나
["ICN","A"]["ICN","B"]["B","ICN"] 에 경우 정렬을 한후에 큐에넣고 방문 처리를 척용하게 되면 모든 티켓을 전부 사용할 수는 없었다.

이 문제는 결국 여행경로의 경우의 수를 전부 다 구해서 리스트로 정렬한 후 가장 앞쪽에 있는 경우의 경로를 배열로 출력하면 되는 문제이다

1. DFS

	private void dfs(String next, String visit, String[][] tickets, int depth) {
        if (tickets.length == depth) {
            answer.add(visit);
            return;
        }
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(next) && !check[i]) {
                check[i] = true;
                dfs(tickets[i][1], visit + " " + tickets[i][1], tickets, depth + 1);
                check[i] = false;
            }
        }
    }

원래는 visited String 을 이런식으로 split하기는 싫었다. 하지만 이유가 있는데, arraylist 로 반환되는 경우에는 재귀로 데이터가 쌓이기 때문에 뽑아 써야하는 타이밍에서 데이터가 엉망진창이 되버리기 때문에 리스트로 받기에는 무리가 존재했다. (이것은 깊은 복사를 사용하면 개선될 수 있다)

음... BFS로 문제를 다시 풀고 싶어서 BFS 풀이를 찾아보았다 블로그 검색을 해서 찾았다. 파이썬 코드지만 매우 알아보기가 쉬웠다.

2. BFS

여기서 어제 공부한 깊은 복사 개념을 사용해보았다. 위에서는 값 복사까지 해서 arraylist를 관리하는 싫었는데 BFS 풀이에서는 이것이 꼭 필요했다

1. 여정을 담을 티켓 객체 구현

	class Ticket {
        String current; // 현재 도착한 위치
        String visited; // 현재까지의 여행 경로
        boolean[] count; // 방문한 여행지

        Ticket(String current, String visited, boolean[] count) {
            this.current = current;
            this.visited = visited;
            this.count = count;
        }
    }

이 문제는 여정마다 방문한 배열이 다르다. 어떤 여행경로는 모든 여행경로를 거치지만, 어떤 배열은 모든 경로를 다 거치지 않고 담길 수 있다. 그 이유는 방문한 여행지의 순서가 전부다르기 때문에 몇번째 티켓을 언제 방문했는지를 담을 수 있는 배열이 따로 필요하다.
하나의 방문 배열로는 감당할 수가 없는 것이다.

2. 방문할 티켓을 큐에 담아 다음 경로를 예측한다

		Queue<Ticket> q = new LinkedList<>();
        // 처음 방문 할 위치는 "ICN" 으로 정해져 있다
        q.add(new Ticket("ICN", "ICN", new boolean[tickets.length]));
        while (!q.isEmpty()) {
            Ticket t = q.poll();
            // 티켓이 모두 방문 했는지의 여부를 체크 하기위해 스트림 함수를 사용하였다
            long c = IntStream.range(0, t.count.length).mapToObj(idx -> t.count[idx]).filter(x -> x == true).count();
            // 티켓이 전부 방문 했다면 이것은 방문 경우의 수 중 하나로 추가된다
            if (c == tickets.length) {
                answer.add(t.visited);
                continue;
            }
            for (int j = 0; j < tickets.length; j++) {
            	// 티켓 방문 여부가 이전 큐에 담겨진 t와 얕은 복사가 발생하기 때문에 깊은 복사를 시도한다.
                boolean[] count = t.count.clone();
                // 이번에 방문할 여행지가 맞고 해당 여행 경로에서 방문을 했는지의 여부를 확인한다
                if (t.current.equals(tickets[j][0]) && !count[j]) {
                    count[j] = true;
                    q.add(new Ticket(tickets[j][1], t.visited + " " + tickets[j][1], count));
                }
            }
        }

이전까지는 깊은 복사의 개념은 조금 난해 했다. 사실 주소 복사의 개념이라는 것은 알고있었는데, 막상 구현할때는 결국 생성자를 다시 생성해서 주입하는 경우로 많이 시도했었다. 그러나 너무 코드 낭비가 심해서 항상 고민이 많았는데, 이렇게 clone 함수를 사용하면 깊은 복사가 가능 하다. 너무 간편하다. 그렇지만.... 파이선에 비해서 숏코딩이 참 힘든거 같다..

전체 코드

전체 코드