[해결완료 !] 😭도와주세요.. 알고리즘 문제풀이..

지인의 도움으로 문제 해결 ! 로직에 문제는 없고.. 당연 반례도 없고.. 그저 코드 딱 한글자 잘못되었다는.. ㅎㅎ.. 디버깅 하면서 왜 몰랐는지 의문입니다 진짜 수십번 .. 했는데 ! 다음 글에 알고리즘 문제풀이 글로 다시 쓰면서 제가 잘못 풀었던 부분도 녹여보겠씁니다 !

여러분 도와주세요.. 오늘 하루 종일 이것만 고민한 것 같아요.. 😭 문제 전문과 풀이 코드는 뒤에 이어지고, 우선 제가 무엇때문에 고충을 겪고 있는지 먼저 설명해 보겠습니다. ( 저는 이미 문제를 알고, 심지어 고민을 몇 시간은 한 후에 작성하는 것이라서 자세히 쓴다고 해도 '아씨 도와달라더니 뭔 소리야;' 싶을 수 있어요 ㅠㅡㅠ 혹 그러시다면 아래에 문제 전문을 보고 오시는 걸 추천드려요 ! )

간단한 문제 설명과 지금 겪고 있는 문제 ❗️

[ 간단한 문제 요약 ]
아래에서 설명할 알고리즘 문제는 결과적으로 그래프에서 모든 노드를 탐색하는 경로중에서 알파벳 순서가 더 빠른 경우를 도출하는 문제입니다.

• 각 노드는 두 단어를 담고있습니다.
• 노드의 연결을 설명하자면, 현 노드의 두 번째 단어와 다른 노드의 첫 번째 단어가 일치한다면 해당 노드로 이동할 수 있습니다.
  • 즉, [A - B]노드에서 [B - A]노드로는 이동할 수 있지만, [A - B]에서 [C - A]로는 이동할 수 없는 것입니다.
  • 전자의 경우 경로는 ABA가 되는 것입니다.
• 아래 문제를 읽고 오셨다면, 저는 티켓 하나를 노드로 보고 문제를 푼 것입니다 !

저는 이 문제를 아래의 1번 방법으로 먼저 풀었습니다. 하지만 테스트 케이스 하나가 틀리다고 나왔고 왜 틀리는지 이해할 수 없었습니다. 후에 혹시나 하는 마음에 2번 방법으로 다시 풀어보았더니 다 맞았다고 나왔습니다.

각 풀이 방법은 아래에 코드를 적으면서 자세히 설명하겠지만, 제가 생각하는 1번과 2번의 유일한 차이는 아래와 같습니다.

• 1번 : 알파벳 순서로 탐색할 수 있도록 미리 정렬하고, 모든 노드를 다 탐색하는 경로 중에서 가장 먼저 나오는 경로를 반환한다.
• 2번 : 모든 노드를 탐색하는 모든 경우를 다 탐색하여 저장해둔 후에 정렬하여 알파벳 순서로 가장 빠른 정답을 반환한다.

저는 1번이 모든 경우를 다 탐색하지 않고 가장 빨리 발견하는 경로를 바로 반환할 수 있어서 시간복잡도 측면에서 더 효율적이라고 생각했습니다. 그러면서도 이 경로가 모든 노드를 탐색할 수 있는 모든 경로 중에서 알파벳 순서로 가장 빠르다는 것을 보장할 수 있도록 미리 두 번째 단어를 기준으로 알파벳순 정렬을 해두었습니다.

두 번째 단어 기준으로 알파벳순 정렬을 하는 것이 경로의 알파벳순이 된다는 것을 보장한다고 생각하는 이유는 아래와 같습니다.

• 문제의 조건으로, 시작 노드의 첫 번째 단어는 특정 단어(우선 A라고 해봅시다!)로 고정되어 있습니다. 그렇기에 시작 노드는 첫 번째 단어가 A이며 두 번째 단어가 가장 빠른 알파벳인 노드일 것입니다.
  ex > [A - B]
• 그렇다면 두 번째 노드의 첫 번째 단어는 첫 번째 노드의 두 번째 단어로 정해지게 되고(대충 B라고 해봅시다!), 세 번째 노드 역시 첫 번째 단어가 B이며 두 번째 단어가 가장 빠른 알파벳인 노드일 것입니다.
  ex > [B - A]
• 저는 두 번째 단어를 기준으로 알파벳 순으로 정렬된 노드들을 순차적으로 탐색하고 있기 때문에, 현 노드의 두 번째 단어와 일치하는 첫 번째 단어를 가진 노드 중 가장 먼저 발견된 노드를 다음 노드로 선정하였습니다.
• 물론 visited는 체크하여서 중복 방문은 없으며, 위와 같은 기준으로 선택한 노드들로 만들어진 경로가 모든 노드를 다 방문하지 않는다면, DFS로 탐색하여 위의 기준에 의하여 그 다음다른 경로를 탐색할 것입니다.

이제 하소연 시작입니다..
도대체 왜 ! 1번 풀이가 틀린지 모르겠습니다 ㅠㅡㅠ

제 생각에 1번은 틀리고 2번이 맞으려면 1번으로 풀었을 때, 즉, 두 번째 단어 순으로 정렬해두고 탐색할 때 모든 노드를 방문하는 가장 먼저 발견한 경로가 모든 노드를 방문하는 모든 경로 중에서 알파벳순으로 가장 빠르지 않다는 것인데..

즉, 두 번째 단어 순으로 정렬해두고 탐색한 최종 경로가 (모든 노드를 방문하는 경로 중에서) 알파벳순으로 가장 빠르다는 것을 보장하지 않는다.. 알파벳순으로 더 빠른 다른 경로가 존재할 수 있다는 것인데..

그런 반례가 도저히 떠오르지 않습니다.. ( 그 반례가 1번 테스트 케이스겠죠.. )

도와주실 의향이 있다면 ❗️

💡 바로 위에 말한 그런 반례가 떠오르시면 알려주세요 !

💡 아니면 위에 설명한 제 생각이나 로직에 오류가 있다면 알려주세요 !

💡 뭐든지 1번 코드가 틀리는 이유를 알려주세요 !

문제 전문

문제 링크

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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 )

import java.util.*;
class Solution {
    public static String[] answer; // 경로가 순서대로 저장될 배열
    public static boolean[] visited; // DFS 방문 체크
    // 모든 경로 탐색하지 않고 첫 번째로 모든 노드 방문 경로가 생기는 경우 탐색을 멈추기 위한 플래그
    public static boolean flag = false;
    
    // DFS 함수
    // param : 티켓 리스트, 시작 티켓의 인덱스, 방문 순서
    public static void dfs(String[][] tickets, int start, int count){
        visited[start] = true; // 첫 노드 방문 체크
        answer[count] = tickets[start][0]; // count번째 경로 넣기
        // 출발지 기준으로 경로를 넣고 있기 때문에
        // 마지막 티켓이라면 도착지를 경로의 마지막으로 넣어주기
        // 그리고 모두 방문한 첫 경로임으로 탐색을 멈추기 위해서 
        // flag 지정 및 return 
        if(count == tickets.length-1){
            answer[count+1] = tickets[start][1];
            flag = true;
            return;
        }
        // 도착지 기준으로 정렬된 순서대로 탐색
        for(int i=0; i<tickets.length; i++){
            // 현재 티켓의 도착지가 출발이면서 ( 다음 티켓 후보 )
            // 사용하지 않는 티켓 찾기 
            if(tickets[i][0].equals(tickets[start][1]) && !visited[i]){
                dfs(tickets, i, count+1); // 재귀적으로 탐색
                if(flag) return; // flag 체크해서 경로 찾았으면 빠르게 종료하기
                // dfs 함수를 빠져나왔으나 flag는 설정되지 않은 경우
                // 즉 해당 경로가 모든 경로를 방문할 수 있는 경우가 아니다
                // 재귀는 빠져나왔고 다음 노드 탐색인데
                // 그러기 위해서 빠져나온 티켓은 사용하지 않은 것이므로 다시 체크 !
                visited[start] = false; 
            }
        }
    }

    public static String[] solution(String[][] tickets) {
        answer = new String[tickets.length+1];
        visited = new boolean[tickets.length];
        // 도착지 기준으로 정렬하기
        Arrays.sort(tickets, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return o1[1].compareTo(o2[1]);
            }
        });
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
            	// ICN이 출발지인 노드가 여러개일때
                // 먼저 위치한, 즉 도착지가 더 빠른 ICN 노드를 시작으로 할 때
                // 모든 노드를 방문할 수 없는 경우를 대비하기 위함
                Arrays.fill(visited, false);
                dfs(tickets, i, 0);
                // 모든 노드를 방문하고 dfs가 종료되었다면 그게 결과니까 종료 !
                if(flag) break;
            }
        }
        return answer;
    }
}

코드 ( 풀이 2 )

import java.util.*;
class Solution {
	// 모든 경로를 문자열 형식으로 저장하는 Arraylist
    public static ArrayList<String> answers = new ArrayList<>(); 
    public static boolean[] visited; // DFS 방문 체크
    
    // DFS 함수
    // param : 티켓 리스트, 시작 나라(ICN), 방문 카운트, 방문 경로 문자열
    public static void dfs(String[][] tickets, String start, int count, String answer){
    	// 시작 나라 경로에 추가
        answer += (start + " ");
        // 모든 티켓 사용 완료이므로 경로리스트에 추가 
        if(count == tickets.length){
            answers.add(answer);
            return;
        }
        for(int i=0; i<tickets.length; i++){
        	// 현재 티켓의 도착지가 출발이면서 ( 다음 티켓 후보 )
            // 사용하지 않는 티켓 찾기 
            if(tickets[i][0].equals(start) && !visited[i]){
                visited[i] = true; // 티켓 사용 체크 
                dfs(tickets, tickets[i][1], count+1, answer); // 재귀 탐색
                // 재귀를 빠져나와서 다른 경로 탐색
                // 그러기 위해서 빠져나온 경로는 방문하지 않은 상태로 다시 체크 !
                visited[i] = false;
            }
        }
    }

    public static String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", 0, "");
        // 모든 노드 방문한 모든 경로를 정렬
        Collections.sort(answers);
        // 가장 앞에 정렬된 것을 최종 결과물의 형태로 변환하여 반환
        return answers.get(0).split(" ");
    }
}