[TIL_Carrotww] 38 - 22/10/26

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 네트워크 level3 dfs 문제
요즘 알고리즘을 너무 안 풀어 머리가 굳어진 것 같다. 원래 알고리즘 하면 머리도 말랑한 느낌이 들고 집중도 잘 됐었는데... 생각보다 오래 걸렸다. 쉬운거 같은데 머리속에서 자꾸 꼬여서... 재귀를 풀때 한 번 생각이 꼬여버리면 다시 가닥을 잡기 어려운 것 같다 ㅠㅜ

• 풀이

def solution(n, computers):
    cnt, visited = 0, []

    def dfs(index):
        visited.append(index)
        for i in range(n):
            if computers[index][i] == 1 and i not in visited:
                dfs(i)

    for i in range(n):
        if i not in visited:
            dfs(i)
            cnt += 1

    return cnt

🧲 python algorithm

🔍 programmers 여행경로 예전에 비슷한 문제를 leetcode에서 풀었었는데 기억 못하는거 보니 난 역시 ㅃ...
예전에 풀때는 5월? 6월인가? 진짜 애송이일때 풀었어서 막막했었는데 지금은 접근 방식이 조금 잘못됐다. 아래 코드가 실패하는 이유는 다음과 같다.
ICN -> AAA
ICN -> BBB
BBB -> ICN
위 케이스가 안되는데 내가 x[0]x[1] 기준으로 정렬을 쫙 하고 result에 넣기 때문에 결과가 다를 수 밖에 없다. 틀리는 이유는 알았으니 시간이 늦은 관계로 내일.. 풀어서 올리려고 한다 ㅎㅎ

• 첫 번째 풀이

from collections import deque

def solution(tickets):
    queue = deque()
    start = tickets[0][0]
    visited = list()
    result = [start]

    tickets.sort(key=lambda x:(x[0],x[1]))

    for i in tickets:
        if i[0] == start:
            queue.append(start)
            break

    while queue:
        temp = queue.pop()
        for ti in tickets:
            if ti[0] == temp and ti not in visited:
                visited.append(ti)
                queue.append(ti[1])
                result.append(ti[1])
                break
    return result