JArchive 프로그래밍 일기

문제 링크 

문제 유의 사항

반드시 모든 티켓을 사용해야 한다. 

반드시 시작 공항은 ICN 이다. 

모든 티켓을 사용할 수 있는 입력만 주어진다. 

가능한 경로가 여러개 나와도, 알파벳순으로 우선하는 경로를 선택한다. (== 탐색 전 정렬 필요) 

리뷰 

DFS 구현 시, 탐색 함수 매개변수와 종료 조건이 중요하다. 

탐색 목표 : 목적지, 몇번째 방문인지. 

탐색 종료 조건 : 티켓 개수가 방문 순서와 똑같으면 모든 티켓을 사용한 것이니까 종료. 

탐색 가능 조건 : 목적지를 시작점으로 하는 티켓이 있는지 확인 && 미방문인지 확인 

1) 모든 티켓을 검사. 

탐색 가능 조건이 있다면, 방문 표시하고 답 벡터에 넣는다. DFS 탐색 시작. 

DFS탐색은 true/ false 를 리턴한다.

탐색 해보고 만약 실패라면, 다시 미방문 표시 

2) 탐색 가능 조건이 없다면, 답 벡터에서 빼고 false 리턴. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

vector<string> routes; // 정답 경로 벡터
bool visit[100002]; // 방문 체크

bool DFS(string start, int cnt, vector<vector<string>> &tickets){

  if(cnt == tickets.size()) return true; // 탐색 끝나면 true

  for(int i = 0; i < tickets.size(); i++){ // 시작점 타겟이 있는지 확인 
    if(visit[i] == false && start == tickets[i][0]){ // 미방문이고, 시작점 타겟이 맞으면, 방문!
      visit[i] = true;
      routes.push_back(tickets[i][1]); // 방문한 도착지를 답 벡터에 푸시
      bool res = DFS(tickets[i][1], cnt+1, tickets);
      if(res) return true;
      visit[i] = false;
    }
  }
  
  routes.pop_back(); // 갈 곳이 없으면, 가장 최근 도착지를 벡터에서 제거 
  return false;
}

vector<string> solution(vector<vector<string>> tickets) {

  sort(tickets.begin(), tickets.end()); // 알파벳 순 앞서는 경로 선택
  routes.push_back("ICN"); // 항상 시작은 ICN
  DFS("ICN", 0, tickets);  //시작점이 "ICN"인 티켓을 탐색

  return routes;
}