[C#] 프로그래머스 DFS 연습 - 여행경로

솔직히 코드 이해는 되지만 백지에서 이렇게 작성할 수 있을지 잘 모르겠다,,

 

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

 

 

using System;
using System.Collections.Generic;

public class Solution {
    
    List<string> answer;
    bool[] visit;

    void dfs(List<string[]> tickets, string cur, List<string> path, int len)
    {
        if (len == tickets.Count)
        {
            if (answer.Count == 0 || string.Join("", path).CompareTo(string.Join("", answer)) < 0)
            {
                answer = new List<string>(path);
            }
            return;
        }

        for (int i = 0; i < tickets.Count; i++)
        {
            if (!visit[i] && tickets[i][0] == cur)
            {
                visit[i] = true;
                path.Add(tickets[i][1]);
                dfs(tickets, tickets[i][1], path, len + 1);
                path.RemoveAt(path.Count - 1);
                visit[i] = false;
            }
        }
    }

    public string[] solution(string[,] ticketsArr)
    {
        int n = ticketsArr.GetLength(0);
        List<string[]> tickets = new List<string[]>();

        // 2차원 배열 → List<string[]> 변환
        for (int i = 0; i < n; i++)
        {
            tickets.Add(new string[] { ticketsArr[i, 0], ticketsArr[i, 1] });
        }

        // **출발 공항을 기준으로 정렬, 같으면 도착 공항 기준으로 정렬 (알파벳순)**
        tickets.Sort((a, b) => a[0] == b[0] ? string.Compare(a[1], b[1]) : string.Compare(a[0], b[0]));

        visit = new bool[n];
        answer = new List<string>();

        // DFS 탐색 시작 (항상 "ICN"에서 시작)
        dfs(tickets, "ICN", new List<string> { "ICN" }, 0);

        return answer.ToArray();
    }
}