Py) 프로그래머스 43164 여행경로

3회차 - 마지막이 좀 찝찝한데 다시 보자

2회차 - 건강한 멘탈로 다시 풀자

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

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

음..그래. 정말 열심히 풀었는데 테스트케이스 2개랑 3번만 맞췄다.

음ㅁ.. 고민 엄청하다가 제출하면 맞출 줄 알았는데 아니었다-

도대체 뭘 생각못한걸까..?

하지만 예전엔 접근도 잘 못하고 정말 싫어하던 bfs dfs를 열심히 푼 나 자신 칭찬해

아래는 틀린코드 (아까우니까 올리기,,)

from collections import deque
def solution(tickets):
    answer = []
    stack = deque([])
    visited = [False for i in range(len(tickets))]

    stack.append(tickets[0][0])   # icn으로 시작합니다

    while stack:
        top = stack.pop()
        answer.append(top)
        for ticket in range(len(tickets)):
            if visited[ticket] == True or tickets[ticket][0] != top:
                continue                        
            else:                               
                if len(stack):                  # stack이 비지 않았다면 하나 pop해서 확인
                    tmp = stack.pop()
                    if tickets[ticket][1] > tmp:   
                        put = tmp
                    else:
                        put = tickets[ticket][1]
                        idx = tickets.index([tickets[ticket][0], tmp])
                        # print(idx)
                        visited[idx] = False
                        visited[ticket] = True
                    stack.append(put)
                else:
                    visited[ticket] = True
                    stack.append(tickets[ticket][1])

    return answer

print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
# print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))

 

참고 중인 코드

def solution(tickets):
    answer = []
    dest = dict()

    for ticket in tickets:
        if ticket[0] in dest:
            dest[ticket[0]].append(ticket[1])
        else:
            dest[ticket[0]] = [ticket[1]]       # []

    for i in dest:
        dest[i].sort(reverse=True)      # 각 리스트 역순

    stack = ['ICN']

    while stack:
        top = stack[-1]
        if top not in dest or len(dest[top]) == 0:
            answer.append(top)
            stack.pop()
        else:                   # 도착지가 있는 애였을 때
            stack.append(dest[top][-1])     # 리스트 맨뒤
            dest[top].pop()

    answer.reverse()
    return answer

print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))

 

김예 다 뿌순다