문제풀이)프로그래머스)c#) 여행경로

여행경로

 

URL : programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

DFS를 사용한 구조로 작업 진행했다.

하다가 여러 번 문제가 생겨서 고쳤는데 이유는 다음과 같다.

 

1. 주어진항공권을 모두 사용해야 한다 (실제로는 모든 경로를 다 우회하는 것이 아닌 가장 길게 갈 수 있는 경로를 만들어야 한다.)

 

2. 재귀하는 과정에서 무한 루프( ex : A -> B ->B -> A)

 

using System;
using System.Collections.Generic;
using System.Linq;
 
 	Queue<string[]> answerQueue = new Queue<string[]>();
    public void DFS(ref string[,] tickets, bool[] visit, int pos,Stack<string> p)
    {

        if(visit.Contains(false))
        { 
            Stack<string> temp;
            for(int i = 0; i< visit.Length; i++)
            {

                if((visit[i] == false) && (tickets[pos,1] == tickets[i,0]))
                {    
                    temp = p;
                    temp.Push(tickets[i,1]);
                    visit[i] = true;
                    DFS(ref tickets,visit, i,temp);
                    visit[i] = false;
                    temp.Pop();
                }
            }
        }
        else
        {
            if(p.Count != visit.Length+1)
                return;

            var temp = p.ToArray();
            Array.Reverse(temp);
            answerQueue.Enqueue(temp);
        }

    }
    public string[] solution(string[,] tickets) {
        int len = (tickets.Length / 2);
        bool[] visit = new bool[len];
        Stack<string> stack = new Stack<string>();
        for(int i = 0; i < len; i++)
        {
            stack.Push(tickets[i,0]);
            stack.Push(tickets[i,1]);
            visit[i] = true;
            DFS(ref tickets,visit, i, stack);
            visit[i] = false;
            stack.Clear();
        }

        //answer
        var answer = answerQueue.Where(x => x[0].Equals(tickets[0,0])).ToArray();
        var temp = answer[0];
        foreach(var v in answer)
        {
            for(int i = 0; i < len+1; i++)
            {
                if(temp[i] != v[i])
                {
                    if(String.Compare(temp[i],v[i])==1)
                        temp = v;
                    break;
                }
            }
        }
        return temp;
    }

 

간단히 DFS를 테스트하는 겸 풀었지만 막상 풀어보니 제약이 너무 많았다.

두 개의 테스트 코드는 바로 통과하는데 실제 제출해보니 문제가 많아서 계속 뜯어고쳤다.

개인적으로는 문제가 예시와 설명이 부족하다.. 비추..

 

 ★☆☆☆☆