여행경로
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,
방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.제한 사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
풀이
public class TravelCourseSelector
{
private static List<string> _travelCourse = new List<string>();
private static List<Ticket> _ticketList = new List<Ticket>();
private const string DEFAULT_START_POS = "ICN";
public static string[] Solution(string[,] tickets)
{
for (int i = 0; i < tickets.GetLength(0); i++)
{
_ticketList.Add(new Ticket(tickets[i, 0], tickets[i, 1]));
}
Travel(DEFAULT_START_POS, new List<string>());
return _travelCourse.ToArray();
}
private static bool Travel(string currentPos, List<string> travelCourses)
{
//최종 목적지를 입력하기 전에는 여행 경로와 전체 티켓의 길이가 동일하므로 종료 조건으로 사용
if (travelCourses.Count >= _ticketList.Count)
{
//최종 위치를 추가
travelCourses.Add(currentPos);
_travelCourse = new List<string>(travelCourses);
return true;
}
//이동한 장소 목록에 추가
travelCourses.Add(currentPos);
//현재 위치와 같은 시작 지점을 가진 티켓 리스트를 확보 = 사용 가능한 티켓 리스트를 확보
List<Ticket> possibleTicketList = _ticketList.Where( t
=> t.StartPos == currentPos
&& !t.IsUsed).ToList();
//사용 가능한 티켓이 없을 경우 탐색을 종료
if (possibleTicketList.Count == 0)
//잘못된 탐색으로 처리하기 위해 false 반환
return false;
//사용 가능한 티켓 리스트를 알파벳 순으로 정렬
possibleTicketList.Sort((t1,t2) => String.Compare(t1.ArrivalPos, t2.ArrivalPos, StringComparison.Ordinal));
//순차적으로 티켓을 사용하며 경로를 탐색
foreach (Ticket ticket in possibleTicketList)
{
//해당 티켓을 사용한 것으로 처리
ticket.IsUsed = true;
//분기 되는 시점에서 새로운 리스트로 분리
//잘못된 탐색으로 false가 반환 될 경우 초기화를 위해
List<string> tempCourses = new List<string>(travelCourses);
if(!Travel(ticket.ArrivalPos, tempCourses))
//백트래킹을 위해 방문 상태를 취소
ticket.IsUsed = false;
else
return true;
}
return false;
}
}
class Ticket
{
public string StartPos { get; private set; }
public string ArrivalPos { get; private set; }
public bool IsUsed { get; set; }
public Ticket(string startPos, string arrivalPos)
{
StartPos = startPos;
ArrivalPos = arrivalPos;
}
}전역 변수
private static List<string> _travelCourse = new List<string>();
private static List<Ticket> _ticketList = new List<Ticket>();
private const string DEFAULT_START_POS = "ICN";- 최종적으로 제출할 전체 여행 코스를 저장할
_travelCourse리스트와 입력된 티켓 정보를 저장할Ticket클래스 리스트_ticketList그리고 시작 지점은 항상"ICN"으로 정해져 있으므로DEFAULT_START_POS로 저장
초기화
public static string[] Solution(string[,] tickets)
{
for (int i = 0; i < tickets.GetLength(0); i++)
{
_ticketList.Add(new Ticket(tickets[i, 0], tickets[i, 1]));
}
Travel(DEFAULT_START_POS, new List<string>());
return _travelCourse.ToArray();
}- 입력받은 2차원 배열인
tickets을Ticket클래스로 저장하여_ticketList에 저장 - 이후
Travel()함수를 재귀적으로 실행해 최종적으로 전체 여행 코스를 작성
Ticket 클래스
class Ticket
{
public string StartPos { get; private set; }
public string ArrivalPos { get; private set; }
public bool IsUsed { get; set; }
public Ticket(string startPos, string arrivalPos)
{
StartPos = startPos;
ArrivalPos = arrivalPos;
}
}- 시작 지점과 도착 지점을 갖고 있으며 백트래킹으로 검사 시 해당 티켓이 사용되었는지 여부를 판단하는
IsUsed라는 boolean 변수를 통해 확인 - 생성자에서 시작 지점과 도착 지점을 입력
Travel() 함수
private static bool Travel(string currentPos, List<string> travelCourses)
{
//최종 목적지를 입력하기 전에는 여행 경로와 전체 티켓의 길이가 동일하므로 종료 조건으로 사용
if (travelCourses.Count >= _ticketList.Count)
{
//최종 위치를 추가
travelCourses.Add(currentPos);
_travelCourse = new List<string>(travelCourses);
return true;
}
//이동한 장소 목록에 추가
travelCourses.Add(currentPos);
//현재 위치와 같은 시작 지점을 가진 티켓 리스트를 확보 = 사용 가능한 티켓 리스트를 확보
List<Ticket> possibleTicketList = _ticketList.Where( t
=> t.StartPos == currentPos
&& !t.IsUsed).ToList();
//사용 가능한 티켓이 없을 경우 탐색을 종료
if (possibleTicketList.Count == 0)
//잘못된 탐색으로 처리하기 위해 false 반환
return false;
//사용 가능한 티켓 리스트를 알파벳 순으로 정렬
possibleTicketList.Sort((t1,t2) => String.Compare(t1.ArrivalPos, t2.ArrivalPos, StringComparison.Ordinal));
//순차적으로 티켓을 사용하며 경로를 탐색
foreach (Ticket ticket in possibleTicketList)
{
//해당 티켓을 사용한 것으로 처리
ticket.IsUsed = true;
//분기 되는 시점에서 새로운 리스트로 분리
//잘못된 탐색으로 false가 반환 될 경우 초기화를 위해
List<string> tempCourses = new List<string>(travelCourses);
if(!Travel(ticket.ArrivalPos, tempCourses))
//백트래킹을 위해 방문 상태를 취소
ticket.IsUsed = false;
else
return true;
}
return false;
}종료 조건
//최종 목적지를 입력하기 전에는 여행 경로와 전체 티켓의 길이가 동일하므로 종료 조건으로 사용
if (travelCourses.Count >= _ticketList.Count)
{
//최종 위치를 추가
travelCourses.Add(currentPos);
_travelCourse = new List<string>(travelCourses);
return true;
}"ICN"에서 시작해 티켓을 하나 사용할 때마다 경로에 값이 하나씩 추가됨- 경로 리스트의 길이가 티켓 리스트의 길이와 같아졌을 때 전체 티켓이 모두 사용된 상황
- 마지막으로 위치한 지점을 경로에 추가하고 전역 변수로 선언된
_travelCourse에 깊은 복사 실시 true값을 반환해 연쇄적으로 재귀 함수가 종료되도록 함
재귀 함수 처리
//이동한 장소 목록에 추가
travelCourses.Add(currentPos);
//현재 위치와 같은 시작 지점을 가진 티켓 리스트를 확보 = 사용 가능한 티켓 리스트를 확보
List<Ticket> possibleTicketList = _ticketList.Where( t
=> t.StartPos == currentPos
&& !t.IsUsed).ToList();
//사용 가능한 티켓이 없을 경우 탐색을 종료
if (possibleTicketList.Count == 0)
//잘못된 탐색으로 처리하기 위해 false 반환
return false;- 입력받은 장소를 이동한 장소 목록에 추가하고 현재 위치에서 출발하면서 아직 사용되지 않은 티켓을 찾아
possibleTicketList에 저장 - 사용 가능한 티켓이 없을 경우 해당 재귀 루트에서는 최종에 도달하는 방법을 찾지 못한 것이므로 잘못된 탐색으로 처리하여
false반환
//사용 가능한 티켓 리스트를 알파벳 순으로 정렬
possibleTicketList.Sort((t1,t2) => String.Compare(t1.ArrivalPos, t2.ArrivalPos, StringComparison.Ordinal));
//순차적으로 티켓을 사용하며 경로를 탐색
foreach (Ticket ticket in possibleTicketList)
{
//해당 티켓을 사용한 것으로 처리
ticket.IsUsed = true;
//분기 되는 시점에서 새로운 리스트로 분리
//잘못된 탐색으로 false가 반환 될 경우 초기화를 위해
List<string> tempCourses = new List<string>(travelCourses);
if(!Travel(ticket.ArrivalPos, tempCourses))
//백트래킹을 위해 방문 상태를 취소
ticket.IsUsed = false;
else
return true;
}- 여러 경로가 가능할 경우 알파벳 순으로 경로를 설정하라는 조건이 있었으므로 사용 가능한 티켓을 알파벳 순으로 정렬
- 이후 사용 가능한 티켓을 순차적으로 사용하여 해당 티켓을 이용 처리 하고, 현재
travelCourses를 깊은 복사하여 임시 여행 경로 리스트tempCourses를 다음 재귀 함수에 전달 - 만약 해당 리스트를 전달받은 재귀 함수에서 실행하던 여행 경로가 완료될 수 없을 경우 해당 분기의 정보를 폐기하기 위해 깊은 복사로 전달
- 재귀 함수를 실행해
true이 1번 반환되면 연쇄적으로 모든 재귀 함수가 종료되며,false가 실행될 경우 해당 티켓의 사용을 취소하고 다음 티켓으로 탐색을 실시 - 만약 모든 티켓에 대해서 탐색을 실패할 경우 이전 분기로 돌아가 다시 탐색을 실시해야하므로 반복문 이후에는 최종적으로
false를 반환
