[TIL_Carrotww] 41 - 22/10/31

📝Carrotww의 코딩 기록장

🧲 python Algorithm

🔍 programmers 여행경로 dfs level3
첫 번째 풀이가 안됐던 이유가 재귀를 통해 다른 단어로 다시 들어가야 하는데 첫 번째 경로로만 들어가 다시 나오지 못했다.

• 1번째 풀이

from collections import defaultdict

def solution(tickets):
    visited, path, stack = [], ["ICN"], ["ICN"]
    tic = defaultdict(list)
    for a, b in tickets:
        tic[a].append(b)
    for t in tic.values():
        t.sort()

    def dfs(visited, path, stack):
        # if not stack:
        #     return path
        start = stack.pop()
        if start in tic:
            for i in tic[start]:
                if (start, i) not in visited:
                    visited.append((start, i))
                    stack.append(i)
                    path.append(i)
                    dfs(visited, path, stack)
                    print(visited)

    dfs(visited, path, stack)

    return path

위 풀이로는 테스트케이스 절반만 통과... 다른 경로로 들어가서 나왔다가 2 번째 경로로 들어가야하는데 그 걸 처리를 못 해줬다.

• 정답 풀이

from collections import defaultdict

def solution(tickets):
    tic = defaultdict(list)
    result = []

    for key, val in tickets:
        tic[key].append(val)
    for i in tic.values():
        i.sort(reverse=True)

    def dfs(city):
        while tic[city]:
            dfs(tic[city].pop())
        if not tic[city]:
            result.append(city)
            return

    dfs("ICN")

    return result

🧲 잡담

🔍 dfs는 스택으로 풀 수 있고, 재귀로 풀 수 있는데 지금 난 재귀로 풀었다.
평소 스택으로 푸는것만 익숙해져있어 재귀로 풀어보았다.
오늘은 강의를 듣느라 시간이 늦어 많이 생각을하고 풀어보지 못했다.
내일 문제 하나 더 풀며 지금 문제도 다른 방향으로 몇 번 더 풀어보아야겠다.