• https://programmers.co.kr/learn/courses/30/parts/12421
• 1, 2, 3번은 이전에 몇 번 풀었던 문제를 다시 풀어보았고,
• 4번은 예전부터 못 풀었던 문제인데 드디어 정답처리를 받았다 ✨

✏️ 1. 타겟 넘버 (Level 2)

from collections import deque


def solution(numbers, target):
    answer = 0
    
    
    q = deque()
    q.append([0, -1])
    
    
    while q:
        sumi, pre_idx = q.popleft()
        ####print(sumi, pre_idx)
        
        
        # 1. 종료 조건
        if pre_idx+1 == len(numbers):
            # (정답에 해당되는 조건)
            if sumi == target:
                answer += 1
                
                
                
        # 2. 다음 큐 방문 진행
        else:
            q.append([sumi + numbers[pre_idx+1], pre_idx+1])
            q.append([sumi - numbers[pre_idx+1], pre_idx+1])
        
        
        
        
    return answer

✏️ 2. 네트워크 (Level 3)

from collections import deque


def solution(n, computers):
    answer = 0
    
    # 1. 인접 리스트 구하기
    a =  []
    
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            
            
            if computers[i][j] == 1:
                u, v = i+1, j+1
                a.append([u, v])
    
    
    ###print(a)
    
    
    # 2. BFS 수행
    q = deque()
    check = [False] * (n+1)
    
    
    while False in check:
        idx = check.index(False)
        check[idx] = True
        
        q = deque() # 큐 리셋
        q.append(idx)
        answer += 1 # 큐를 새로 생성할 때마다 네트워크의 개수(cnt)를 1 증가시켜주면 됨 !
        
        
        while q:
            x = q.popleft()
            
            for case in a:
                u, v = case
                
                if u == x and check[v] == False:
                    q.append(v)
                    check[v] = True
                    
                    
        
    ###print(check)
    
    
    
    
    return answer -1

✏️ 3. 단어 변환 (Level 3)

from collections import deque



def change(x, y):
    cnt = 0
    n = len(x)

    for i in range(n):
        if x[i] != y[i]:
            cnt += 1
            
    
    if cnt == 1:
        return True
    else:
        return False
    

def solution(begin, target, words):
    answer = []
    
    if target not in words:
        return 0
    
    
    
    m = len(words)
    
    for idx in range(m):
        if change(begin, words[idx]) == True:
            # 큐 생성 및 BFS 탐색 시작 !
            q = deque()
            q.append((words[idx], 1))
            
            check = [False] * m
            check[idx] = True
            
            
            
            
            while q:
                pre_word, depth = q.popleft()
                
                
                # 종료 조건
                if pre_word == target:
                    answer.append(depth)
                    break
                    
                
                for j in range(m):
                    if check[j] == False and change(pre_word, words[j]) == True:
                        q.append((words[j], depth+1))
                        
                        
                                        
    
    
    return min(answer)

✏️ 4. 여행 경로 (Level 3)

• 문제 해결과정 및 코드 : https://github.com/sallyy1/Algorithm/issues/137
• 가장 처음에 가능한 경우의 수가 여러 개라는 점에서 브루트포스 문제로 접근해 permutations을 활용해 풀어보았으나 4개 중 1번에서 시간초과로 역부족이었다.
• 그래서 역시 deque를 활용해 접근을 했는데, 다양한 예제 테스트케이스에 Global하게 맞는 해답을 찾기까지 여러 시행착오를 겪었다.
• 개선점: 풀이들을 찾아보니 stack를 활용하면 간단하게 문제를 풀 수 있는 방법이 있다고 한다..! ✨

from collections import deque


def solution(tickets):
    answer = []
    
    ## 1. 주어진 항공권은 모두 사용해야 합니다. (키 조건)  
    ## 2. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
    
    m = len(tickets)
    
    tickets.sort() ## 1번만 틀렸습니다. 나오다가 알파벳 순서를 미리 반영하기 위해 정렬 한 줄을 추가해 주었더니 바로 통과..!
    
    
    for i in range(m):
        u, v = tickets[i]
        
        if u == "ICN": ## 항상 "ICN" 공항에서 출발합니다.
            check = [False] * m
            check[i] = True
            
            q = deque() 
            q.append(([u, v], check)) # 시작 공항(2개 짝), 어느 항공권을 사용했는지 표시 배열
            ####print('--시작-- ', i, q)



            while q:
                pre_q, pre_c = q.popleft()
                ####print(q)


                if False not in pre_c: ## 종료 조건
                    if pre_q not in answer:
                        answer.append(pre_q)
                        break


                for idx in range(m):
                    if pre_c[idx] == False and pre_q[-1] == tickets[idx][0]:
                        ###q.append((pre_q, pre_c)) (디버깅) 1번. 현재 항공권 이용 안 하는 경우 빼주어야 5번에서 무한루프 해결됨..?

                        # 2번.
                        copy = pre_c[:] ## (디버깅) 이전 방문표시 배열(항공권에 대한)을 복사해주고 사용해야 함
                        copy[idx] = True
                        
                        c = pre_q[:]
                        c.append(tickets[idx][1])

                        q.append((c, copy))
                
    
    answer.sort()
    return answer[0]