[Lv.3] 여행경로 [프로그래머스_코딩테스트] [DFS, 백트래킹] [30분]

🔍 문제 요약

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

프로그래머스

ICN 항공으로 시작해서 티켓을 모두 사용한 여행경로를 짜려고 할 때 여행경로를 반환하는 문제. 항공권 정보는 출발지와 도착지로 해서 2차원 배열로 구성되어 있다 (tickets) (추가로 여러 경로가 가능한 경우 알파벳 순서로 한다)

🧠 나의 접근 방식과 시행착오

이 문제는 DFS로 풀려고 시도를 하였으나 결국 문제를 복잡하게 풀다가 못 푼 문제. visited도 넣고 백크래킹 작동까지 고민하긴 하였으나 제대로된 풀이에 도달하진 못하였다. 풀이코드 부분에서 피드백을 보고 학습

✅ 풀이 코드

문제를 풀려고 시도했던 방향 자체는 크게 다르지 않았던 것으로 보이긴 한다. 다만 DFS 문제에 익숙치 않다 보니 제대로 풀지 못했던 듯 하다. 일단 이미 방문했던 것을 거르기 위한 visted와 인자로 받은 tickets, 그리고 경로를 저장하기 위한 List<string> route가 있다. (필자는 queue로 하려고 시도는 했었다.) 그리고 필자의 경우 모든 경우를 구한 후에 나중에 사전순 정렬을 하려고 했지만 그렇게 되면 복잡해질 수 있는지 문제에선 2차원 배열을 먼저 알파벳 순서로 정렬을 하고 시작을 하였다. DFS를 호출할 때 인자로 depth를 넣어주는 것 또한 핵심포인트로 보인다. BFS도 그랬지만 종료 시점을 결국 알아야 하기에 depth와의 비교를 하는 부분이 꼭 필요하다. 그렇게 해서 맞는 티켓을 찾게 되면 DFS로 재귀호출을 해서 시도를 하고 아까 depth가 티켓을 모두 사용한 수치와 동일한 경우 true로 반환을 하여 재귀를 멈추게 if문을 걸어둔 것을 알 수 있다. 그 if문 후에는 백트래킹 (티켓 선택 전으로 돌리기)를 위해서 visited를 false로 원복하고 removeAt으로 Route를 넣었던 것도 돌린다.

using System;
using System.Collections.Generic;

public class Solution {
    private List<string> route = new List<string>();
    private bool[] visited;
    private string[,] tickets;
    private string[] answer;

    public string[] solution(string[,] inputTickets)
    {
        int ticketCount = inputTickets.GetLength(0);
        tickets = inputTickets;
        visited = new bool[ticketCount];

        // 티켓들을 사전순 정렬
        Array.Sort(tickets, (a, b) => 
        {
            int cmp = string.Compare(a[0], b[0], StringComparison.Ordinal);
            if (cmp == 0)
                return string.Compare(a[1], b[1], StringComparison.Ordinal);
            return cmp;
        });

        // DFS 시작
        route.Add("ICN");
        DFS("ICN", 0);

        return answer;
    }

    private bool DFS(string current, int depth)
    {
        if (depth == tickets.GetLength(0))
        {
            answer = route.ToArray(); // 정답 복사
            return true; // 경로 완성되면 더 이상 안 탐색
        }

        for (int i = 0; i < tickets.GetLength(0); i++)
        {
            if (!visited[i] && tickets[i, 0] == current)
            {
                visited[i] = true;
                route.Add(tickets[i, 1]);

                if (DFS(tickets[i, 1], depth + 1)) return true; // 경로 찾았으면 종료

                // 백트래킹
                visited[i] = false;
                route.RemoveAt(route.Count - 1);
            }
        }

        return false;
    }
}

🔄 정리

DFS와 BFS는 정말 많이 풀고 익숙해지는 것을 목표로 해야 할 듯 하다. 재귀와 visted 체크까지만 생각을 했었으나 그 내부에서 백트래킹까지 더해지고 반복문이 들어가고 if문이 섞이고 하는 부분들로 복잡해질 수 있으나 많이 풀다 보면 익숙해질 것으로 생각된다. 추가로 DFS의 경우 결국 종료시점을 정해줘야 하므로 Depth를 넣어주는 것이 핵심. 추가로 DFS를 호출시 인자로는 변동이 되는 요소 current와 depth만을 주고 나머진 전역변수로 할당하고 처리를 하고 있는 점 역시 중요한 포인트로 생각이 된다.