프로그래머스. 여행경로

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

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

 

dfs로 풀었다.

주의할점이 있는데 가능한 경로 중 알파벳 순서 상 앞서는 경로를 무조건 적으로 먼저 방문해서는 안된다.

그래프가 일방 통행이 있는 방향 그래프이기 때문에 모든 티켓을 소진하지 못할수도 있다.

 

티켓이 다음과 같이 주어지면 

vector<vector<string>> tickets =
        {
                {"A", "B"},
                {"A", "C"},
                {"C", "A"}
        };

A: B, C

C: A

 

만약 A에서 시작해서 B로 먼저 가면 B로부터 갈 수 있는 곳이 없기 때문에 모든 티켓을 소진하지 못한다.