Algorithm/Java

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

dbfl9911 2024. 10. 14. 20:20
반응형

https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

- 문제 풀이

 

1.변수 선언 및 초기화

  • list: 모든 가능한 경로를 저장하는 리스트입니다. 탐색을 마친 경로는 여기에 저장됩니다.
  • visited: 각 항공권이 사용되었는지 여부를 기록하는 배열입니다. 이미 사용한 티켓을 다시 사용하지 않도록 하기 위한 배열입니다.
import java.util.*;

class Solution {
    // 방문한 경로들을 저장할 리스트
    static ArrayList<String> list = new ArrayList<>();
    // 항공권 사용 여부 기록하는 배열
    static boolean visited[];
    
    
    .... 
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];

 

 

 

 

 

2.DFS 탐색 함수 (dfs) 정의

이 함수는 현재 공항에서 출발하여, 가능한 다음 목적지로 이동하며 경로를 찾는 재귀적인 탐색입니다.

  • depth: 현재까지 사용한 티켓의 수를 나타냅니다. 모든 티켓을 다 사용하면 탐색을 종료합니다.
  • now: 현재 위치하고 있는 공항입니다. 출발할 공항을 의미합니다.
  • path: 현재까지 거쳐온 경로를 저장하는 문자열입니다. 경로는 공백을 기준으로 구분합니다.
  • tickets: 항공권 정보를 담고 있는 2차원 배열입니다. 각 티켓은 [출발지, 도착지]로 되어 있습니다.
  static void dfs(int depth, String now, String path, String[][] tickets) {
public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        // DFS 탐색 시작: 초기 상태는 "ICN" 공항에서 출발하고, 경로도 "ICN"으로 시작
        dfs(0, "ICN", "ICN", tickets);

 

 

 

 

 

3. DFS 로직 설명

  • 기저 조건: depth가 tickets.length와 같으면, 즉, 모든 티켓을 다 사용한 경우에는 탐색을 종료합니다. 이때까지 지나온 경로(path)를 list에 추가합니다.
  • 현재 공항에서 출발하는 티켓 탐색:
    • 모든 티켓을 순회하면서, 아직 사용하지 않은 티켓 중 출발 공항이 현재 공항과 일치하는 티켓을 찾습니다.
    • 해당 티켓이 조건에 맞다면 visited[i] = true로 설정해 사용한 티켓임을 표시하고, 그 티켓의 목적지로 이동하여 다시 DFS를 호출합니다.
    • 목적지로 이동할 때, 경로도 업데이트해 path + " " + tickets[i][1]처럼 목적지를 이어 붙여 나갑니다.
  • 백트래킹: 모든 경로를 탐색하기 위해 DFS 재귀 호출이 끝나면, 다시 그 티켓을 사용하지 않은 상태로 돌려놓습니다 (visited[i] = false). 이렇게 해야 다른 경로에서도 해당 티켓을 사용할 수 있게 됩니다.
static void dfs(int depth, String now, String path, String[][] tickets) {
        // 모든 티켓을 다 사용하면
        if (depth == tickets.length) {
            // 해당 경로(path)를 리스트에 추가하고 종료
            list.add(path);
            return;
        }

        // 현재 공항(now)에서 출발하는 모든 티켓을 탐색
        for (int i = 0; i < visited.length; i++) {
            // 티켓이 아직 사용되지 않았고, 출발 공항이 현재 공항과 일치하는지 확인
            if(!visited[i] && now.equals(tickets[i][0])) {
                visited[i] = true;
                // 재귀 호출: 목적지로 이동하고, 경로 업데이트
                dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);

                // 해당 티켓을 자시 사용 가능한 상태로 되돌림(백트래킹)
                visited[i] = false;
            }
        }
    }

 

 

 

 

4. 메인 함수 (solution) 설명

  • visited 배열은 항공권의 수만큼 크기를 설정하고, 아직 아무 티켓도 사용하지 않았으므로 초기값은 모두 false입니다.
  • DFS 탐색을 시작하는데, 출발 공항은 항상 "ICN"이므로 처음 호출은 dfs(0, "ICN", "ICN", tickets)로 시작합니다. 경로의 시작도 "ICN"입니다.
  • 모든 가능한 경로가 list에 저장되면, 이를 알파벳 순서로 정렬합니다. 문제에서 요구한 조건대로 가장 알파벳 순서상 앞서는 경로가 최종 경로가 됩니다.
  • 경로는 공백으로 구분되어 있으므로, 이를 split(" ")하여 문자열 배열로 반환합니다.
public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        // DFS 탐색 시작: 초기 상태는 "ICN" 공항에서 출발하고, 경로도 "ICN"으로 시작
        dfs(0, "ICN", "ICN", tickets);
        // list에 저장된 경로들 알파벳 순으로 정렬
        Collections.sort(list);
        // 가장 알파벳 순서 앞서는 경로 선택해서 공백 기준으로 나눈 후 리턴
        return list.get(0).split(" ");
    }

 

+ Collections.sort() 정렬 부분 ?

알파벳 순서로 정렬하는 것은 ICN에서 출발한 후 나머지 공항들에 대한 순서를 의미합니다. 즉, 경로 중간에 등장하는 공항들이 알파벳 순서로 가장 앞서는 경로를 찾는 것입니다.

 

예시로 설명:

티켓을 사용하여 다음과 같은 경로들이 완성되었다고 가정해 봅시다:

  1. "ICN SFO ATL ICN ATL SFO"
  2. "ICN ATL SFO ICN SFO ATL"

이 경로들을 Collections.sort(list)로 정렬하면, 경로는 다음과 같이 정렬됩니다:

  1. "ICN ATL SFO ICN SFO ATL"
  2. "ICN SFO ATL ICN ATL SFO"

즉, "ICN"에서 출발하는 것은 고정이고, "ICN" 이후의 경로들이 알파벳 순서로 정렬됩니다.

 

 

- 정답 코드

import java.util.*;

class Solution {
    // 방문한 경로들을 저장할 리스트
    static ArrayList<String> list = new ArrayList<>();
    // 항공권 사용 여부 기록하는 배열
    static boolean visited[];

    static void dfs(int depth, String now, String path, String[][] tickets) {
        // 모든 티켓을 다 사용하면
        if (depth == tickets.length) {
            // 해당 경로(path)를 리스트에 추가하고 종료
            list.add(path);
            return;
        }

        // 현재 공항(now)에서 출발하는 모든 티켓을 탐색
        for (int i = 0; i < visited.length; i++) {
            // 티켓이 아직 사용되지 않았고, 출발 공항이 현재 공항과 일치하는지 확인
            if(!visited[i] && now.equals(tickets[i][0])) {
                visited[i] = true;
                // 재귀 호출: 목적지로 이동하고, 경로 업데이트
                dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);

                // 해당 티켓을 자시 사용 가능한 상태로 되돌림(백트래킹)
                visited[i] = false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        // DFS 탐색 시작: 초기 상태는 "ICN" 공항에서 출발하고, 경로도 "ICN"으로 시작
        dfs(0, "ICN", "ICN", tickets);
        // list에 저장된 경로들 알파벳 순으로 정렬
        Collections.sort(list);
        // 가장 알파벳 순서 앞서는 경로 선택해서 공백 기준으로 나눈 후 리턴
        return list.get(0).split(" ");

    }
}
반응형