- 문제 출처 : 프로그래머스
- 문제명 : 여행경로
- 분류 : DFS, Sort
- 언어 : Java
- 체감 난이도 : ⭐⭐⭐⭐⭐
- 풀이 시간 : 2h~
- Fail Cnt : 3
- String 타입 자료에 대해 DFS 탐색을 학습할 수 있으며, 문제를 바탕으로 모든 경우의 수를 고려하도록 학습할 수 있음. 정렬 학습 가능
알고리즘 설계
1. 프로세스 설계
<solution 메소드>
- 동일한 출발지를 가지는 티켓을 정리한다.
ex) A -> B, A -> C, B -> D 에 대해
A -> B, C
B -> D
와 같이 저장 - 각 출발지에 대한 목적지들을 오름차순 정렬한다
- 정렬 결과를 활용해서 DFS탐색한다.
- 정렬 결과를 answer 배열에 저장한다.
< dfs_search(String from, int idx) 메소드 >
- 인자로 들어온 출발지를 경로 배열(g_route)에 저장한다.
g_route(idx) <- from - 만일 전체 여행 경로 수만큼 저장했다면 더이상 DFS를 재귀호출하지 않고 종료한다. 이는 목적지들을 미리 오름차순 정렬했기 때문에 가능하다.
- 만일 전체여행 경로 수만큼 탐색하지 않았으면 인자로 들어온 출발지의 목적지들을 순차적으로 탐색한다.
(1) 탐색시 방문 안한 목적지가 있을 경우, 방문 처리하고 DFS 재귀호출을 통해 방문한다.
(2) 재귀호출이 끝나면 방문 처리했던것을 원래 상태로 원상복구한다.
2. 테스트통과 코드
1) 2차원 String 배열 활용해 풀이한 코드
- 전역 변수
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)에 저장된다.
- solution 메소드
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;
}- dfs_searching 메소드
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; }
}
}
}
}
}2) HashMap을 활용해 Key : Value 가 1 : N 형식을 띄도록 풀이한 코드
- 전역 변수
//하나의 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) |
- solution 메소드
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;
}- dfs_search 메소드
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; }
}
}
}
}3. Fail했던 이유
TC 1, 2를 계속 통과하지 못했고 이유를 알 수 없어 질문을 찾아보았다.
Fail이 떳던 이유는 모든 티켓을 다 써야하는데 이를 고려하지 않아 DFS 방문시, 첫번째 목적지에 대해서만 DFS 방문을 했기 때문이었다.
다음과 같은 TC에 대해
[["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]
정답은
["ICN", "COO", "ICN", "BOO", "DOO"]
인데 오답
["ICN", "BOO", DOO"]
을 출력했다.
따라서 방문 처리를 통한 모든 경우의 수를 탐색하도록 코드를 수정했다.
안녕하세요😀😀