https://school.programmers.co.kr/learn/courses/30/lessons/43164
문제
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
| tickets | return |
|---|---|
| [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] | ["ICN", "JFK", "HND", "IAD"] |
| [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] |
입출력 예 설명
예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.
풀이
import java.util.*;
import java.lang.*;
class Solution {
static class Edge{
String to;
boolean visit;
Edge(String to, boolean visit){
this.to = to;
this.visit = visit;
}
}
static List<String> res = new ArrayList<>();
static int N; // 전체 항공편 갯수
public String[] solution(String[][] tickets) {
N = tickets.length;
HashMap<String, List<Edge>> adjEdge = new HashMap<>();
for(String[] t: tickets){
adjEdge.putIfAbsent(t[0], new ArrayList<Edge>());
List<Edge> temp = adjEdge.get(t[0]);
temp.add(new Edge(t[1], false));
adjEdge.put(t[0], temp);
} // end input
dfs("ICN", adjEdge, new ArrayList<String>(), 1);
String[] answer = new String[res.size()];
for(int i=0; i<res.size(); i++)
answer[i] = res.get(i);
return answer;
}
static void dfs(String now, HashMap<String, List<Edge>> adjEdge, List<String> loads, int depth) throws Exception{
List<Edge> edges = adjEdge.get(now);
loads.add(now);
if(edges!=null){ // !
for(int i=0; i<edges.size(); i++){
Edge e = edges.get(i);
if(!e.visit){
List<Edge> tempEdges = new ArrayList<>(edges);
tempEdges.remove(i);
tempEdges.add(new Edge(e.to, true)); // visit처리
HashMap<String, List<Edge>> copyOfAdjEdge = new HashMap<>();
for (Map.Entry<String, List<Edge>> entry : adjEdge.entrySet()) {
copyOfAdjEdge.put(entry.getKey(), entry.getValue());
}
copyOfAdjEdge.put(now, tempEdges); // 간선리스트 재정의
dfs(e.to, copyOfAdjEdge, new ArrayList<>(loads), depth+1);
}
}
}
if(depth < N+1) return; // 모든 항공편을 방문
if(res.size()==0){
res = loads;
return;
}
for(int i=0; i<loads.size(); i++){
int compareResult = loads.get(i).compareTo(res.get(i));
if(compareResult < 0){
res = loads;
break;
} else if(compareResult > 0){ // !!! 이 경우도 생성
break;
}
}
return;
}
}단방향 그래프이므로 노드의 방문을 검사하는 boolean 배열의 visit배열을 쓰면 안된다
-> 그러면(향하는 노드, 방문여부)값을 가지는Edge클래스를 만들어 인접리스트로 만들어야 한다.
-> 그러고 방향을 따라 탐색할 때 인접리스트에서 시작노드에서 접점노드로의 탐색이 된 적 있다고 마킹한다.
이 아이디어를 구상하고 DFS에 적용했을 때 문제가 있었다.
방문처리 하는 것 까지는 좋았는데 인접리스트 Map과 그안의 value (List<Edge>) 는 dfs에 다시 넘겨줄 때마다 깊은 복사를 해야한다. 그렇지 않으면 재귀의 갈래마다 다른 상태(?) 를 가지고 있어야 하는데 그렇지 못한다.
List<Edge> tempEdges = new ArrayList<>(edges); tempEdges.remove(i); tempEdges.add(new Edge(e.to, true)); // visit처리 HashMap<String, List<Edge>> copyOfAdjEdge = new HashMap<>(); for (Map.Entry<String, List<Edge>> entry : adjEdge.entrySet()) { copyOfAdjEdge.put(entry.getKey(), entry.getValue()); } copyOfAdjEdge.put(now, tempEdges); // 간선리스트 재정의 dfs(e.to, copyOfAdjEdge, new ArrayList<>(loads), depth+1);상당히 스파게티인 코드지만......
현재 분기에 도착한 노드에서 방문하지 않은 인접한 노드를 검사하고 거기로 간 다음에 "방문처리" 하는 코드이다. 이 부분에서 죄다 깊은 복사를 해야 한다
List든 Map이든 객체라서 객체에 의한 참조가 일어나기 때문에..
이런 기본적인 것도 몰랐다니.
결과
1번이 원래 저러나..?
후기
객체를 함수에 넘기면 객체에 대한 참조(reference)를 전달하기 때문에 함수 내부에서 값을 변경하는 등 변화를 주면 호출자에게도 영향이 감
그외에도
else if(compareResult > 0){ // !!! 이 경우도 생성
break;
} 마지막에 분기별 경로 결과끼리 비교할 때 이 부분을 안써서 계속 틀렸는데
분기별 결과와 전역변수로 둔 결과(즉 지금까지 정해진 정답)를 비교하면서 전역변수로 둔 결과가 조건에 맞을수도 있으니 그에 대한 조건문을 또 써야 함
이전문제인 양궁대회 문제에서도 안해서 틀림 ㅠ.ㅠ
