[깊이/너비 우선 탐색(DFS/BFS)] Level 3 여행 경로

문제 설명

• 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
• 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

 

---

안녕하세요

하루라도 코테를 안하면 다 까먹어버리는 똥멍충이입니다~😇

분명 DFS/BFS 공부했는데 고새 까먹었네요 하하

때려주고 싶지만 얼른 정리나 하겠습니다~^^

 

 

풀이)

이 문제는 DFS로 해결하였다

주로 모든 경로를 탐색할 땐 DFS, 최단 경로는 BFS를 사용한다고 '나는' 그렇게 알고있다

사실 확실치도 않아서 많은 문제를 풀어보며 확인해볼 예정이다

암튼 이 문제는 DFS로 풀었다

DFS는 스택을 사용해서 푸는데, 재귀함수 자체가 스택과 동일한 역할이기 떄문에 DFS 재귀함수를 구현하였다

 

음 코드를 보면서 설명하도록 하겠다

 

자바 코드)

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    static ArrayList<String> list = new ArrayList<String>();
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length];
        
        int index=0;
        dfs(index, "ICN", "ICN", tickets);
        
        Collections.sort(list);
    
        answer = list.get(0).split(" ");
        return answer;
    }
    
    public void dfs(int index, String start, String result, String[][] tickets) {
        if(index == tickets.length) {
            list.add(result);
            return;
        }
        
        for(int i=0;i<tickets.length;i++) {
            if(!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;
                dfs(index+1, tickets[i][1], result+" "+tickets[i][1], tickets);           
                visited[i] = false; //방문 기록 초기화
            }
        }
        return;
    }
}

먼저 dfs 함수를 보자

index 파라미터와 티켓 배열의 길이가 같으면 이를 list에 추가한다

이 때 list는 정답이 될 수 있는 여행 경로를 문자열로 만들어서 저장하는 String 배열이다

여기서는 하나의 여행 경로를 "한국 미국 중국 러시아" 이런식으로 띄어쓰기를 통해 하나의 String으로 생성하고, 만약 전체 여행지를 방문하였다면 이를 list 배열에 저장하는 것이다

이는 문제에서 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하라고 하였기 떄문에 이를 위해 모든 경로를 저장해준다

그리고 나중에 이를 정렬하여 맨 앞에 있는 여행 경로를 answer로 반환해주는 것이다!

 

암턴 그 아래는 dfs 동작 과정이다

dfs는 총 4개의 파라미터를 받는다

먼저 index는 현재 이동한 여행지의 갯수로, dfs를 호출할 때마다 하나씩 추가해주는 것이다 (dfs를 호출한다는 것은 다른 도시를 방문한 것이므로)

그리고 start는 현재 여행지로, 여기서 출발할 거라 start라고 붙였다

result는 여행 경로를 한 줄로 저장한 문자열로, 하나의 여행경로가 끝나면 이를 list 배열에 추가한다

마지막으로 tickets 배열을 전달받는다

 

자 이제 동작 과정이다

먼저 티켓 배열을 모두 반복하며 검사한다

만약 방문하지 않았고(!visited[i]) 현재 위치와 반복문을 통해 만난 tickets의 출발지가 동일하다면 여행이 가능하다

따라서 현재 ticket을 방문처리를 해주고, 다음 여행지로 이동하기 위해 dfs 함수를 재귀호출한다

이 때 도시를 이동하는 거니까 index+1을 하고 start는 현재 반복문에서 만난 tickets의 도착지(tickets[i][1])이 된다

그리고 result에는 다음 여행지를 띄어쓰기와 함께 붙여준다

아무튼 이런 과정을 계속해서 반복하면 list에는 아래와 같이 여행 경로가 저장되게 된다

2번쨰 테스트 케이스의 경우 총 3가지의 여행 경로가 가능하게 된다

이를 sort 함수를 통해 정렬해주고, 맨 앞의 여행경로를 반환해주면 끝!

 

 

dfs를 사알짝 변형해서 풀면 되었다

난 처음에는 그때 그때 비교해서 알파벳 순서대로 여행지를 방문하려고 했는데, 그냥 모든 경로를 구하고 여기서 제일 먼저 있는 애를 반환하는게 더 쉬운 것 같다

암튼 이해는 완료!

알는 파이썬 코드다!!

 

 

 

파이썬 코드)

list = [] #가능한 여행경로를 모두 저장

def solution(tickets):
    answer = []
    visited = [False]*len(tickets) #티켓 개수만큼 방문 여부 생성
    index = 0
    
    dfs(index, "ICN", "ICN", tickets, visited)
    
    list.sort() #알파벳 순서대로 정렬
    #print(list)
    answer = list[0].split(" ") 

    return answer

def dfs(index, start, result, tickets, visited):
    #print(index, result)
    if index == len(tickets): #모든 여행지를 방문한 경우
        list.append(result) #여행 경로 저장
        return
    
    for i in range(len(tickets)):
        if visited[i]==False and tickets[i][0] == start:
            visited[i] = True
            dfs(index+1, tickets[i][1], result+" "+tickets[i][1], tickets, visited)
            visited[i]=False

파이썬도 자바랑 같은 알고리즘으로 풀었다~~

 

결과는 모두 통과!

 

---

참고 블로그

https://tosuccess.tistory.com/36

[프로그래머스 level_3] 여행경로 for JAVA