[프로그래머스] 여행경로

문제

[프로그래머스] 여행경로

실패 코드

from collections import deque

def bfs(start, new_tickets):
    queue = deque()
    length = len(new_tickets)+1
    queue.append(start) # 출발지, 도착지
    
    while queue:
        route = queue.popleft()
        print(route)
        
        if len(route) == length:
            return route
        
        for ticket in new_tickets:
            if ticket[0] == route[-1]:
                route.append(ticket[1])
                new_tickets.remove(ticket)
                queue.append(route)
    
    return 0
            
        

def solution(tickets):
    answer = []
    
    candidate = []
    
    for ticket in tickets:
        if ticket[0] == "ICN":
            candidate.append(ticket)
    
    for i in candidate:
        new_tickets = tickets[:]
        result = bfs(i,new_tickets)
        if result != 0:
            answer.append(result)
        
    answer.sort()
    return answer[0]

• BFS로 풀었는데 제출 시 테케 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","COO","DOO","BOO","DOO","COO","BOO","ICN","BOO"]
• 그냥 new_tickets 돌면서 되면 넣고 안되면 안넣고 하다보니 모든 항공권 쓸 수 없는 경우가 생김(모든 항공권을 쓸 수 있는 경우임에도)
• queue에 각 route에 따른 현재 남은 티켓(now_t)을 추가해주어 해결했다.

정답 코드

from collections import deque

def bfs(start, new_tickets):
    queue = deque()
    length = len(new_tickets)+1
    queue.append((start,new_tickets))
    
    
    while queue:
        route, now_t = queue.popleft()
        
        if route is None:
            continue
        
        if len(now_t) == 0:
            if route not in answer:
                answer.append(route)
            continue

        for ticket in new_tickets:
            if ticket in now_t:
                if ticket[0] == route[-1]:
                    result = route[:]
                    result.append(ticket[1])
                    t = now_t[:]
                    t.remove(ticket)
                    queue.append((result, t))
        

    return 0
            
        

def solution(tickets):
    global answer
    answer = []
    
    candidate = []
    
    for ticket in tickets:
        if ticket[0] == "ICN":
            candidate.append(ticket)
    
    for i in candidate:
        new_tickets = tickets[:]
        new_tickets.remove(i)
        bfs(i,new_tickets)
        
    answer.sort()
    return answer[0]

정리

• 어찌어찌 BFS로 풀었지만 티켓 크기가 커지면 DFS로 푸는 것이 더 효율적인 것 같다
• 근데 DFS는 아직 익숙해지지 않아서 DFS 연습을 좀 해야겠다

DFS vs BFS

1. DFS

• 조건에 따른 경우의 수를 구할 때
• 이동 과정에 제약이 있을 때

2. BFS

• 최단 거리
• 미로 찾기
• BFS는 경로의 특징을 갖지 못한다.