[미완] 프로그래머스: 여행경로 ( python, 파이썬 )

1. 문제

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

코딩테스트 연습 - 여행경로

2. 풀이

생각나는 대로...

bfs 구현해서 모든 경우를 다 살펴보고 각 경우마다 그때의 answer list와 cnt_dic(중복된 숫자를 셈)을 가져와서 구현한다.

 

3. 구현

1. dict에서 특정 value 제거할 때

dic['key'].remove(val)

2.

TypeError: object of type 'NoneType' has no len() 이 에러가 많이 났는데

lis.append('sth') 자체를 list로 취급해서 그랬다.

lis.append('sth')을 print해보면 NoneType이 나오는데 append 한 결과 자체는 NoneType, 즉 아무것도 return 하지 않는다.

 

 

지금 실력으로는 1번 시간초과 뜨는 것 해결을 못하겠다.

우선 구현한 것 까지하고 다시 풀 예정

from collections import deque
import copy

def solution(tickets):
    answer = []
    dic={}
    cnt={}
    s = set()
    for a, b  in tickets:
        if a in dic:
            dic[a].append(b)
        else:
            dic[a]=[b]
        if (a,b) not in cnt:
            cnt[(a,b)]=1
        else:
            cnt[(a,b)]+=1
    q= deque()
    visit={}
    q.append(("ICN", ["ICN"], cnt))
    visit["ICN"]=True
    while q:
        
        cur = q.popleft()
        if cur[0] not in dic:
            continue
        for iter in dic[cur[0]]:
            tmp_lis = copy.deepcopy(cur[1])
            tmp_cnt = copy.deepcopy(cur[2])
            
            if tmp_cnt[(cur[0], iter)]==0:
                continue
            else:
                tmp_lis.append(iter)
                tmp_cnt[(cur[0], iter)]-=1

            if len(tmp_lis)==len(tickets)+1:
                answer.append(tmp_lis)
            else:
                q.append((iter, tmp_lis, tmp_cnt))
                
    answer = sorted(answer)
    return answer[0]