[프로그래머스] 여행 경로 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=java

프로그래머스

 

문자열, DFS

 

 

출발지와 도착지가 나와있는 비행기 티켓이 N개 주어지고, 이 티켓을 모두 써서 갈 수 있는 경로를 구하는 문제

경로가 여러개라면, 사전순을 먼저 방문하는 경로로

 

접근 방법

 

1. 출발지를 key로, 출발지에서 갈 수 있는 도착지들을 value로 갖는 인접리스트를 만든다. (HashMap사용)

2. 인접리스트에 모든 티켓을 반영한 후에, value들만 사전순으로 정렬한다.

3. ICN을 시작으로 DFS

 

DFS 재귀함수

- 매개변수로 path(현재까지의 경로), now(현재 출발지), cnt(사용한 티켓 수), adj(인접리스트, 단, 사용한 티켓의 도착지는 삭제된)을 갖는다.

- path에 지난 경로를 저장하고, adj에는 이미 방문한 즉, 이미 사용한 티켓의 도착지는 value에서 삭제한다.

- 우선, cnt를 확인하여 총 티켓수와 같으면 모든 티켓을 사용한 것이므로 answer에 담는다. 

(단, 여기서 answer가 사전순을 먼저 방문하는 경로여야 한다. 이를 위해서 인접리스트의 도착지들이 사전순으로 정렬되어 있었기 때문에, DFS 로직상 먼저 모든 티켓을 사용하는 경로가 사전순을 먼저 방문한 경로가 된다. -> 최초로 티켓을 다쓰는 경로가 최종 경로가 되어야 하기 때문에, answer가 비어있을 때만 경로가 갱신될 수 있도록 했다.)

- 티켓을 아직 다 사용하지 않은 경우, now의 가능한 도착지들을 방문해야한다.

- adj.get(now)로 도착지들을 순회하며 하나씩 경로에 추가하여 다시 dfs를 호출해야 하는데,

이때 path는 현재까지의 경로 + 새로운 도착지를 추가해서 dfs에 넘겨줘야하고, now는 새로 방문할 도착지로 변경된다. 사용한 티켓수는 1증가하고, adj 인접리스트에는 새로 방문할 도착지를 빼줘야한다. (이래야 이미 사용한 티켓을 다시 사용하는 경우를 막을 수 있는데..)

 

자바에서 Map이나 ArrayList나 다 참조타입으로 전달돼서, 값을 지우고 다시 매개 변수로 보내려면

깊은 복사를 해야하는데요.

Map<String, List<String>> newAdj = new HashMap<>();
adj.forEach((key, value) -> {
    newAdj.put(key, new ArrayList<>(value));
});

이렇게 forEach를 써주면 아주 편합니다.

(key, value)를 읽어서 다시 newAdj에 key와 value를 다시 put해 주는 식입니다.

 

swift에서는 딕셔너리도 값 타입이라 그냥 넘겨도 되는데 말이죠.

 

암튼 이렇게 깊은 복사를 해서 newAdj만든 다음 adj가 아닌 newAdj에서만 새로 방문할 도착지를 지우고 dfs의 매개변수로 담아서 호출해주면 됩니다.

그니까, ICN -> HND 이런 티켓이면 ICN : {HND, SFO} 이렇게 adj에 담겨있었는데, HND를 빼주는 거죠. 그래야 다시 ICN에 방문했을 때 HND를 다시 방문하지 않게 되겠죠. 만약 방문하면 인천이랑 하네다만 무한반복하게 됨;

 

암튼 이걸 구현하고 싶었구요.

 

이 다음은 경로를 갱신해주어야 하는데요.

현재까지의 경로 path에 dest(새로운 도착지)를 추가해 주어야 해요.

저는 path를 , 로 구분된 문자열로 만들어서 마지막에 반환할 때만 split으로 배열로 바꿔줄 예정이라

path+","+dest 방식을 사용했습니다.

 

깨달음

1. 문자열 배열에서 계속 값을 갱신해야할 때는 그냥 문자열을 + 구분자를 사용해서 나중에 split 하는 것이 더 편하다.

2. collection 타입은 깊은 복사하기 까다로우니 참고할 것

3. 딕셔너리는 자바에서 Map의 구현체 HashMap, put(key, value), get(key) 등 사용, 순회하려면 entrySet() or .forEach 사용, ArrayList는 값으로 remove(값)이 된다. 인덱스도 됨. get(key)했는데 없으면 null반환

4. ArrayList sort는 Collections.sort(list) 사용

 

소스코드

import java.util.*;

class Solution {
    
    int cntTickets = 0;
    String answer = "";
    
    public void dfs(String path, String now, int cnt, Map<String, List<String>> adj) {
        if(cnt == cntTickets && answer == "") {
            answer = path;
            return;
        }
        
        if(adj.get(now) != null) {
            for(String dest: adj.get(now)) {
                Map<String, List<String>> newAdj = new HashMap<>();
                adj.forEach((key, value) -> {
                    newAdj.put(key, new ArrayList<>(value));
                });
                // adj에서 지우고
                newAdj.get(now).remove(dest);
                
                // dfs 호출
                dfs(path+","+dest, dest, cnt+1, newAdj);
            }
        }
        
    }
    
    public String[] solution(String[][] tickets) {
        cntTickets = tickets.length;
        
        Map<String, List<String>> adj = new HashMap<>();
        // 인접리스트 만들기 adj
        for(int i = 0 ; i < tickets.length ; i++) {
            if(adj.get(tickets[i][0]) != null) {
                adj.get(tickets[i][0]).add(tickets[i][1]);
            } else {
                List<String> dest = new ArrayList<>();
                dest.add(tickets[i][1]);
                adj.put(tickets[i][0], dest);
            }
        }
        
        adj.forEach( (a,b) -> {
            Collections.sort(b);
        });
        
        // dfs
        dfs("ICN", "ICN", 0, adj);
                
        return answer.split(",");
    }
}