| 문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
입출력 예 설명 예제 #1 [ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다. 예제 #2 [ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다. |
네트워크 문제와 유사하지만 조금 더 어려운 것 같습니다. 모든 티켓을 다 써서 모든 경로를 다 방문했을 경우가 정답이 되므로 깊이를 우선적으로 탐색해야하는 DFS 문제임을 알 수 있습니다.
* 전체 코드
package pojoPrj;
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String[]> resultList;
public String[] solution(String[][] tickets) {
resultList = new ArrayList<>();
String[] result = new String[tickets.length + 1];
boolean[] used = new boolean[tickets.length + 1];
for (int i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0].equals("ICN")) {
// 첫번째 티켓 정보는 미리 담아두고 재귀 함수 호출
result[0] = tickets[i][0];
result[1] = tickets[i][1];
// 재귀함수 호출
// 해당 티켓을 사용한 경우와 사용하지 않았을 경우를 모두 체크해줘야 함
used[i] = true;
dfs(tickets, used, 2, tickets[i][1], result);
used[i] = false;
}
}
// 배열 오름차순 정렬
resultList.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i].compareTo(o2[i]) > 0) {
return 1;
} else if (o1[i].compareTo(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫번 째 리턴
return resultList.get(0);
}
private void dfs(String[][] tickets, boolean[] used, int resultIdx, String pre,
String[] result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx == result.length) {
String[] temp = new String[result.length];
for (int i = 0; i < result.length; i++) {
temp[i] = result[i];
}
resultList.add(temp);
return;
}
for (int i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같다면
if (!used[i] && tickets[i][0].equals(pre)) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
}
}
먼저 "ICN"에서 가장 먼저 출발해야하고 "ICN"이 출발지인 티켓이 몇 장일지는 알 수 없습니다. 또한 문제에서 요구하는 리턴 조건을 보면 리턴 배열의 첫 번째는 꼭 "ICN"이 들어가야 합니다. 즉 "ICN"이 있는 티켓은 출발지와 도착지를 모두 배열에 남겨야 하고 나머지 티켓들은 도착지만 배열에 남겨야 한다는 의미입니다.
이렇게 이해하는 것이 중요한 이유는 재귀함수를 통해 DFS를 수행하려면 항상 똑같은 조건이 필요하다는 것입니다. 당연하게도 같은 함수를 계속 호출하므로 같은 내용이 수행되기 때문입니다.
따라서 이번 문제에서는 단순하게 재귀함수를 짜면 안되고 가장 첫 티켓(출발지가 "ICN")일 경우 처리를 약간 다르게 해줘야 합니다. 재귀함수 안에서 조건절을 걸어줄 수도 있고 첫 재귀함수 호출 전에 "ICN"티켓을 따로 처리한 뒤 재귀함수를 호출해줘야 합니다. 저는 후자의 방법으로 작성했습니다.
일단 여러 결과가 나올 수 있으므로 결과를 모두 담아줄 List를 만들어줍니다. 그리고 첫 티켓을 선택할 반복문을 설정해줍니다. 첫 티켓은 출발지가 "ICN"인 모든 티켓으로 설정해야합니다. 그리고 이 티켓이 처음 사용될 때마다 모든 경우의 수를 찾는 재귀함수가 시작돼야 합니다.
package pojoPrj;
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String[]> resultList;
public String[] solution(String[][] tickets) {
resultList = new ArrayList<>();
String[] result = new String[tickets.length + 1];
boolean[] used = new boolean[tickets.length + 1];
for (int i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0].equals("ICN")) {
// 최초 출발지마다 재귀함수 호출 수행
}
}
그리고 한번의 재귀함수에 사용할 결과 배열을 생성해주고, 티켓의 사용 여부를 체크해줄 boolean 배열도 생성해줍니다. 한번 사용한 티켓은 다시 사용하면 안되기 때문에 상태값을 설정해주는 용도입니다.
첫번 재 티켓 정보를 result 배열에 넣어준 뒤 사용 처리를 하고 재귀함수를 호출해줍니다. 티켓을 사용해 모든 경우의 수를 탐색한 뒤, 다른 "ICN" 티켓을 사용하는 경우로 넘어가기 전에 다시 티켓 사용여부를 false로 바꿔줘야 하는 점에 주의해야 합니다. 재귀함수를 이용한 DFS에 가장 흔하게 사용되는 방법입니다. 자신이 있을 경우와 없을 경우를 모두 탐색하는 것이죠.
package pojoPrj;
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String[]> resultList;
public String[] solution(String[][] tickets) {
resultList = new ArrayList<>();
String[] result = new String[tickets.length + 1];
boolean[] used = new boolean[tickets.length + 1];
for (int i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0].equals("ICN")) {
// 첫번째 티켓 정보는 미리 담아두고 재귀 함수 호출
result[0] = tickets[i][0];
result[1] = tickets[i][1];
// 재귀함수 호출
// 해당 티켓을 사용한 경우와 사용하지 않았을 경우를 모두 체크해줘야 함
used[i] = true;
dfs(tickets, used, 2, tickets[i][1], result);
used[i] = false;
}
}
이제 DFS를 수행할 재귀함수를 작성할 차례입니다. 티켓을 타고 들어가는 재귀함수이므로 더 이상 타고 갈 티켓이 없으면 자동으로 리턴되기 때문에 탈출문이 따로 필요 없습니다. 대신 모든 티켓을 다 사용해 결과 배열을 가득 채운 경우라면 결과 리스트에 추가해줘야하기 때문에 일단 이 부분을 먼저 작성해줍니다.
result 배열의 인덱스가 length와 동일해졌다는 것은 인덱스를 벗어난 상태라는 것이므로 더 이상의 배열 작업은 하지 않고 리턴시켜주면 됩니다. 리턴 시키기 전에 결과 리스트에 최종 배열을 담아줘야 하는데, 여기서 주의할 점은 매개변수로 받은 result 배열을 바로 담아주면 안된다는 것입니다.
객체는 메모리 주소를 담고 있는 참조변수이기 때문에 새로 new을 사용해 만들어주지 않는 이상 딱 하나밖에 없습니다. C언어의 포인터와 동일한 개념입니다. 따라서 그냥 result 배열을 담았을 경우 앞으로 수행되는 다른 재귀함수에서 계속 내용을 바꾸게 되기 때문에 새로운 배열을 하나 생성해 복사해둔 뒤에 리스트에 붙여줘야 합니다.
private void dfs(String[][] tickets, boolean[] used, int resultIdx, String pre,
String[] result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx == result.length) {
String[] temp = new String[result.length];
for (int i = 0; i < result.length; i++) {
temp[i] = result[i];
}
resultList.add(temp);
return;
}
재귀함수의 나머지 부분입니다. 처음 재귀함수를 호출했을 때와 유사합니다. 이전 티켓의 도착지 정보를 매개변수로 받았으므로 반복문으로 도착지와 동일한 출발지를 가진 티켓을 검색해 도착지를 결과배열에 담아주고 다시 재귀함수를 호출합니다.
위와 동일하게 티켓을 사용했을 때의 모든 경우의 수를 탐색한 뒤에는 다시 티켓 사용 여부를 false로 바꿔줘서 다른 경우의 수에서 해당 티켓을 사용할 수 있도록 만들어줘야 합니다.
private void dfs(String[][] tickets, boolean[] used, int resultIdx, String pre,
String[] result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx == result.length) {
String[] temp = new String[result.length];
for (int i = 0; i < result.length; i++) {
temp[i] = result[i];
}
resultList.add(temp);
return;
}
for (int i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같다면
if (!used[i] && tickets[i][0].equals(pre)) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
}
모든 경우의 수를 다 찾았고, 리스트에 모든 결과 배열이 담겼습니다. 문제에서는 결과가 여러개일 경우 알파벳 순으로 가장 작은 경우를 제출하라고 했으므로 배열 객체들을 오름차순으로 정렬해주면 됩니다.
배열 객체를 정렬하는 방법은 아래글에 자세히 나와있습니다.
[JAVA/- 라이브러리(API)] - Comparator를 사용한 문자열 정렬 및 여러 개의 배열 객체 정렬
// 배열 오름차순 정렬
resultList.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i].compareTo(o2[i]) > 0) {
return 1;
} else if (o1[i].compareTo(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫번 째 리턴
return resultList.get(0);
}
* 전체 코드
package pojoPrj;
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String[]> resultList;
public String[] solution(String[][] tickets) {
resultList = new ArrayList<>();
String[] result = new String[tickets.length + 1];
boolean[] used = new boolean[tickets.length + 1];
for (int i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0].equals("ICN")) {
// 첫번째 티켓 정보는 미리 담아두고 재귀 함수 호출
result[0] = tickets[i][0];
result[1] = tickets[i][1];
// 재귀함수 호출
// 해당 티켓을 사용한 경우와 사용하지 않았을 경우를 모두 체크해줘야 함
used[i] = true;
dfs(tickets, used, 2, tickets[i][1], result);
used[i] = false;
}
}
// 배열 오름차순 정렬
resultList.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i].compareTo(o2[i]) > 0) {
return 1;
} else if (o1[i].compareTo(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫번 째 리턴
return resultList.get(0);
}
private void dfs(String[][] tickets, boolean[] used, int resultIdx, String pre,
String[] result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx == result.length) {
String[] temp = new String[result.length];
for (int i = 0; i < result.length; i++) {
temp[i] = result[i];
}
resultList.add(temp);
return;
}
for (int i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같다면
if (!used[i] && tickets[i][0].equals(pre)) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
}
}
'▸알고리즘 문제 풀이' 카테고리의 다른 글
| 프로그래머스_스택/큐_다리를 지나는 트럭 (JAVA) (0) | 2020.04.20 |
|---|---|
| 프로그래머스_스택/큐_탑 (JAVA) (0) | 2020.04.20 |
| 프로그래머스_DFS/BFS_단어 변환 (0) | 2020.04.17 |
| 프로그래머스_DFS/BFS_네트워크 (0) | 2020.04.17 |
| 프로그래머스_DFS/BFS_타겟 넘버 (0) | 2020.04.17 |
댓글