43164: 여행경로[DFS/BFS]

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

---

1. 문제

• 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
  항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

---

2. 문제의 조건

• 항상 "ICN" 공항에서 출발.
• 3 <= n <= 10,000
• 모든 항공권을 소비해야함.
• 가는 경로가 2개 이상 일 경우, 알파벳 순서를 우선시 함.
• 모든 도시를 방문할 수 없는 경우는 없음.

 

---

3. 문제 접근

• 주의 사항
  
  무조건 "ICN"에서 출발해야한다는 조건과 [A, B]일 경우 A -> B로 가는데 B -> X로 가는 경우가 없을수도 있습니다.

 

• 아이디어
  
  전형적인 DFS문제입니다. 많은 경험을 하다보면 재귀(DFS)에 대한 감이 옵니다.
  
  저의 아이디어는 모든 항공권을 소비해야함으로 남은 항공권의 개수를 파악하고 남은 항공권이 없다면 그것이 정답이 됩니다.
  또한 항공권이 남아있다면, 현재 가지고있는 항공권으로 어딜 갈 수 있는지 파악하고 재귀를 수행합니다.
  만약 항공권이 남아있는데, 조건 사항과 같이 B ->  X로 가는 경우가 없을 수도 있으므로 재귀가 끝난 후에는 다시 탐색하기 위해 돌려주어야합니다.

 

---

4. 풀이 방법

• 모든 항공권 정보를 dict<list>에 넣습니다.
• 모든 항공권의 정보의 list를 오름차순으로 sort합니다.
• 'ICN'부터 탐색을 시작하는데 결과를 반환하기위한 list를 하나 더 만들어줍니다.
  모든 항공권을 소비해야함으로 결과값의 크기는 모든 항공권의 개수와 같습니다.
• 재귀 함수 작성합니다.
  만약 모든 항공권의 개수가 0일 경우, 모든 항공권을 소비했으므로 그것이 정답이니 return 해줍니다.
  항공권의 개수가 1개라도 존재하면 B->X로 가는 항공편이 있는지 확인하고 항공편에 대해 탐색을 진행합니다.
  우선 항공편을 방문했으면 list에서 지워주고 재귀를 반복합니다.
  만약 모두 방문하지 못하여 None으로 return 되었을 경우 [파이썬은 리턴 값이 없으면 None을 자동으로 반환함] 오름차순을 유지하면서 list에 다시 insert해줍니다. (이전부터 다시 반복해야하기 떄문)

 

---

5. 소스코드

• cjw-git.tistory.com/133

 

---

 

cjw.git@gmail.com