[Python] 프로그래머스 여행경로 | DFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

 

문제 해결 과정

- 티켓은 한 번만 사용할 수 있으므로 사용했음을 기록해야함 (하지만, 중복이 있을 수 있음)

- 특정 공항에서 갈 수 있는 공항을 올림차순으로 관리

- DFS로 순환하면서 정답이 될 수 있는 첫번째 경우를 반환

 

- 주의 사항

1. 티켓은 한 번만 사용할 수 있지만, 동일한 경로의 티켓이 2개 이상일 수 있음 ( 2번 테케)

2. 특정 공항에서 다른 공항으로 갈 수 없는데 해당 공항을 저장하지 않았다면 런타임에러가 발생할 수 있음 ( 1번 테케 )

 

- 추가해 볼 테케

입력	결과
[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]	["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]
[["ICN", "BBB"], ["BBB", "ICN"], ["ICN", "AAA"]]	["ICN", "BBB", "ICN", "AAA"]

 

작성 코드

def solution(tickets):
    route = ['' for _ in range(len(tickets)+1)]
    ticket = {}
    used = {}
    for t1, t2 in tickets:
        ticket[t1] = ticket.get(t1, []) + [t2]
        used[(t1, t2)] = used.get((t1, t2), 0) + 1
    
    for t in ticket:
        ticket[t].sort()
    
    def dfs(count, city):
        route[count] = city
        if count == len(tickets):
            return True
        
        if city in ticket:
            for c in ticket[city]:
                if used[(city, c)] > 0:
                    used[(city, c)] -= 1
                    if dfs(count+1, c):
                        return True
                    used[(city, c)] += 1
        return False
    
    dfs(0, "ICN")
        
    return route

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚