[프로그래머스] 여행경로(깊이우선탐색)

프로그래머스

DFS(깊이우선탐색)

 

프로그래머스

여행경로

 

문제 정리

1. 주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다.
2. 항상 "ICN"공항에서 출발
3. 항공권 정보가 담긴 2차원 배열, 방문하는 공항 경로를 배열에 담아 return
4. 모든 공항은 알파벳 3글자인 대문자
5. [a, b]는 a공항에서 b공항으로 가는 항공권이 있다는 의미
6. 주어진 항공권은 모두 사용하며, 가능한 경로가 2개라면 알파벳 순서로 return
7. 모든 도시를 방문할 수 없는 경우는 없다.

 

 

시작하기 전 접근 방법

1. 깊이우선탐색을 이용하여 하나씩 모든 과정을 탐색한다.
2. 탐색여부를 확인하기 위한 visited배열 생성
3. 탐색한 경로를 저장할 List 생성
4. 탐색 조건 : 방문하지 않은 항공권과 현재 도시가 다른 배열에 출발 도시와 같은지 확인한다.
4-1. 조건문이 true이면 방문여부 visited배열을 true로 바꾼다.
5. 재귀함수 dfs를 다시 호출해서 현재 도시를 [x][1]로 매개변수를 대입하고 cnt를 1 증가하며, 나중에 list에 정리할 때 순서를 이어서 대입하기 위한 현재 도시 + " " + 다음도시를 저장할 String매개변수
6. 배열 마지막까지 반복하고 다른 경우와 목표 경로를 찾기 위해 이전 상태로 돌아가기 위해 dfs재귀함수가 다 끝나면 false로 변경한다.
7. list를 정렬하여 첫 번째 인덱스에 해당하는 list가 알파벳순서가 빠른 순이기 때문에 get(0)과 " "로 지역을 분리했기 때문에 " " 부분을 잘라서 return 한다.

 

입출력 예제

 

 

1. 방문 여부 확인하기 위한 boolean타입 배열과 방문 도시를 저장할 ArrayList 생성

import java.util.*;
class Solution {
    static boolean[] visited;
    static ArrayList<String> list = new ArrayList<>();
.........
}

 

 

2. dfs 메서드에 대한 반복조건과 탈출 조건
시작하기 전 접근 방법에 대한 4~7번에 해당

public static void dfs(String[][] tickets,String nowCity, int cnt, String cityList){
        if(cnt==tickets.length){
            list.add(cityList);
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(!visited[i]&&nowCity.equals(tickets[i][0])){
            visited[i] = true;
                dfs(tickets,tickets[i][1],cnt+1,cityList+" "+tickets[i][1]);
                visited[i]=false;
           }
        }
    }

 

 

3. 문제에서 처음 시작은 ICN이기 때문에 처음 dfs매개변수에는(방문하는 공항 경로 배열, 시작공항 ICN, 반복할 깊이를 나타낼 cnt, 방문한 항공권 list)를 매개변수로 가진다.
4. 리스트에 저장된 경우의 수에서 알파벳순을 제일 빠른 걸 반환하기 위한 Collections.sort 정렬
5. 가장 처음 인덱스를 출력하고 리스트에 " "를 기준으로 대입했기 때문에 반환할 때는 해당 영역을 없애고 출력한다.

  public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets,"ICN",0,"ICN");
        Collections.sort(list);
        return list.get(0).split(" ");
    }

 

 

최종 코드

import java.util.*;
class Solution {
    static boolean[] visited;
    static ArrayList<String> list = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets,"ICN",0,"ICN");
        Collections.sort(list);
        return list.get(0).split(" ");
    }
    public static void dfs(String[][] tickets,String nowCity, int cnt, String cityList){
        if(cnt==tickets.length){
            list.add(cityList);
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(!visited[i]&&nowCity.equals(tickets[i][0])){
            visited[i] = true;
                dfs(tickets,tickets[i][1],cnt+1,cityList+" "+tickets[i][1]);
                visited[i]=false;
           }
        }
    }
}