<solution 메소드>
< dfs_search(String from, int idx) 메소드 >
int g_routeCnt = 1; //경로의 총 개수
String[] g_route = {}; //DFS를 실행하며 경로를 저장
int endFlag = 0; //DFS 종료 플래그
String[][] airport = new String[10002][10002]; //airport[idx1][0] -> 출발지 저장, airport[idx1][1~..] -> 출발지로부터 목적지들 저장
int[] idxTable = new int[10002]; //airport 인덱스 저장
만일 A->B, A->C, A->D, B->Z 인 티켓들이 입력으로 주어진 경우 airport 배열은 다음과 같이 저장된다.
|행\열|0열|1열|2열|3열|..|
|---|---|---|---|---|---|
|0행|A|B|C|D|null|
|1행|B|Z|null|null|null|
|2행|null|null|null|null|null|
|..|null|null|null|null|null|
그리고 i행에 대한 인덱스(요소 개수)는 **idxTable(i)**에 저장된다.
public String[] solution(String[][] tickets) {
String[] answer = {};
int startNum = 0; int existFlag = 0;
//airport 초기화
for(int i=0; i<tickets.length; i++) {
existFlag = 0; //같은 출발지가 있으면 1로 변경
for(int j=0; j<startNum; j++) {
if(airport[j][0].equals(tickets[i][0])) {
existFlag = 1;
airport[j][idxTable[j]] = tickets[i][1]; //목적지 저장
idxTable[j] += 1;
break;
}
}
if(existFlag == 0) { //해당 출발지로 첫번째 나온 티켓이면
airport[startNum][0] = tickets[i][0];
airport[startNum][1] = tickets[i][1];
idxTable[startNum] = 2;
startNum++;
}
}
//airport 목적지들 정렬
for(int i=0; i<startNum; i++) {
Arrays.sort(airport[i], 1, idxTable[i]);
g_routeCnt += (idxTable[i] - 1);
}
//dfs 함수 호출을 통해 여행 경로 설정
g_route = new String[g_routeCnt];
dfs_searching("ICN", 0, startNum);
//DFS 탐색 결과를 저장
answer = new String[g_routeCnt];
for(int i=0; i<g_routeCnt; i++) {
answer[i] = g_route[i];
}
return answer;
}
public void dfs_searching(String start, int idx, int startNum) {
g_route[idx] = start;
//경로 총 개수를 만족하면 재귀호출 종료
if(idx+1 == g_routeCnt) {
endFlag = 1; return;
}
//경로 총 개수를 만족하지 않으면 start를 출발지로 가지는 행에 대해 dfs탐색
for(int i=0; i<startNum; i++) {
if(airport[i][0].equals(start)) {
for(int j=1; j<idxTable[i]; j++) {
if(!(airport[i][j].equals("Visited"))) { //방문 안한곳
String next = airport[i][j];
airport[i][j] = "Visited";
dfs_searching(next, idx+1, startNum);
//원상 복구
airport[i][j] = next;
//경로 찾으면 종료
if(endFlag == 1) { return; }
}
}
}
}
}
//하나의 key에 value 여러개 매달기
HashMap<String, ArrayList<String>> g_airport = new HashMap<String, ArrayList<String>>();
String[] g_route = {}; //DFS탐색을 통해 여행경로 저장
int g_routeCnt = 1; //총 방문해야할 여행지의 수 저장
int g_flag = 0; //DFS 탐색이 종료되어야 할 경우 1로 update
만일 A->B, A->C, A->D, B->Z 인 티켓들이 입력으로 주어진 경우 g_airport는 다음과 같이 자료를 저장한다
|Key|Value(ArrayList)|
|---|---|
|A|(B, C, D)|
|B|(Z)|
public String[] solution(String[][] tickets) {
String[] answer = {};
int i, j;
//그래프 정보로 입력받아서 g_airport 초기화
for(i=0; i<tickets.length; i++) {
if(g_airport.containsKey(tickets[i][0])) { //이미 값이 있으면 ArrrayList 뒤에 매달기
ArrayList<String> list = g_airport.get(tickets[i][0]);
list.add(tickets[i][1]);
g_airport.put(tickets[i][0], list);
} else { //해당 키가 처음이면
ArrayList<String> list = new ArrayList<String>(); //객체 생성하고
list.add(tickets[i][1]);
g_airport.put(tickets[i][0], list);
}
}
//g_airport key별로 value 정렬
Set<String> keySet = g_airport.keySet();
Iterator<String> keyIterator = keySet.iterator();
while(keyIterator.hasNext()) {
String key = keyIterator.next();
ArrayList<String> list = g_airport.get(key);
//라우팅 경로 카운팅
g_routeCnt += list.size();
Collections.sort(list);
g_airport.put(key, list);
}
//정렬 결과를 활용해서 DFS 탐색
g_route = new String[g_routeCnt];
dfs_search("ICN", 0);
//정렬 결과 answer로 넣기
answer = new String[g_routeCnt];
for(i=0; i<g_routeCnt; i++) {
answer[i] = g_route[i];
System.out.println(answer[i]);
}
return answer;
}
public void dfs_search(String from, int idx) {
//경로 저장
g_route[idx] = from;
//모든 경로를 저장한 경우 DFS 종료
if(idx+1 == g_routeCnt) {
g_flag = 1; return;
}
//모든 경로를 저장하지 않은 경우 from을 Key로 가지는지 확인해서, 해당 출발지로부터 방문하지 않은 목적지들을 DFS탐색
if(g_airport.containsKey(from)) {
ArrayList<String> list = g_airport.get(from);
for(int i=0; i<list.size(); i++) {
//방문하지 않은 경우 방문표시하고 재귀호출
if(list.get(i) != "Visited") {
String next = list.get(i);
list.set(i, "Visited");
g_airport.put(from, list);
dfs_search(next, idx+1);
//이전 dfs_search() 호출로 모든 경로를 저장했으면 종료
if(g_flag == 0) {
list.set(i, next);
g_airport.put(from, list);
} else { return; }
}
}
}
}
TC 1, 2를 계속 통과하지 못했고 이유를 알 수 없어 질문을 찾아보았다.
Fail이 떳던 이유는 모든 티켓을 다 써야하는데 이를 고려하지 않아 DFS 방문시, 첫번째 목적지에 대해서만 DFS 방문을 했기 때문이었다.
다음과 같은 TC에 대해
[["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]
정답은
["ICN", "COO", "ICN", "BOO", "DOO"]
인데 오답
["ICN", "BOO", DOO"]
을 출력했다.
따라서 방문 처리를 통한 모든 경우의 수를 탐색하도록 코드를 수정했다.