[프로그래머스/Python] Level 3_여행 경로

📌문제 유형

DFS/BFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

- (실패) 50점

from collections import deque
import copy 

def solution(tickets):
    ans = []
    cnt = 0
    q = deque(tickets)
    
    while cnt < len(tickets):
        answer = []

        if cnt > 0:
            q.append(q.popleft())

        t = copy.deepcopy(q)
        
        tmp = 0
        while t:
            tmp += 1

            if tmp > (len(tickets)-1) * 2:
                break

            a,b = t.popleft()

            if len(answer) == 0:
                answer.append(a)
                answer.append(b)
                continue

            if a != answer[-1]:
                t.append([a,b])
            else:
                answer.append(b)
        
        if len(t) == 0:
            ans.append(answer)
        cnt += 1
    
    ans.sort()
    
    return ans[0]

 

 

📌다른사람의 문제풀이

- BFS, DFS 두 개의 풀이

 

여행 경로 - 파이썬(Python)

# BFS
from collections import deque
def solution(tickets):
    answer = []
    q = deque()
    q.append(("ICN",["ICN"], []))
    
    while q:
        airport, path, used = q.popleft()

        if len(used) == len(tickets):
            answer.append(path)
        
        for idx, ticket in enumerate(tickets):
            if ticket[0] == airport and not idx in used:
                q.append((ticket[1], path+[ticket[1]], used+[idx]))
                
    
    answer.sort()

    return answer[0]

 

📌리뷰

- queue에 (현재 위치, 경로, 방문 인덱스)로 저장해서 queue에 있는거 다 쓸때까지 반복

- queue에 어떤 정보를 담을 것인지 고민하기!!!!