1. DFS/BFS 를 왜 쓰는지? 어쩔때 쓰는지? 이해가 가장 어려웠다.
2. 트리 구조로 문제를 푸는 것은 왜 하는지 알겠는데, 완전 탐색이랑 다른 점이 무엇인지?
3. 그냥 모든 경우의 수를 푸는데 있어서 트리 구조를 활용하여 효율적으로 계산한다. 정도로 이해했다.
4. 아래 문제만 봐도 직전 부모 노드의 값을 활용해서 자식 노드의 값을 계산하니까 말이다.

타겟 넘버

1. 이건 이진 트리 문제라고 생각했다.
2. 따라서 levels 라고 붙인 리스트를 만들어주고서
3. 각 레벨로 넘어갈 때 이전 레벨에서 구한 sum 값을 활용한다.
4. 이때 +1 또는 -1 값을 활용하므로 노드가 갈리는 것으로 생각했고 levels에 표현했다.

def solution(numbers, target):
    
    levels = []
    
    for i,num in enumerate(numbers):
        levels.append([i,num,-1*num])
        
    count = 0
    i = 0
    summation = 0
    # print(levels)
    def dfs(i, levels, summation, sign):
        
        summation = summation + levels[i][sign]
        # print(f'i : {i}, levels[i] : {levels[i]}, summation : {summation}')

        nonlocal count
        if i == len(numbers)-1: # 5.lv 이면서 카운트가 타겟이랑 같다면
            if summation == target:
                count = count + 1
            
            return
        
        dfs(i+1, levels, summation,1)
        dfs(i+1, levels, summation,2)
        
    dfs(0,levels, summation, 1)
    dfs(0,levels, summation, 2)
    
    
    print('count : ', count)
    return count

네트워크

1. 못풀어서 다른 사람의 답을 봤다.
2. 요지는, 연결된 노드들을 쭈르륵 방문하고나서 1로 카운트를 구현할건데
3. ** 한번 방문한 노드는 이미 연결됐다는 뜻이므로 이후 방문을 하지 않으면서
4. 한번도 방문하지 않은 노드는 새로운 네트워크이므로 방문을 이어가면서 모두 방문하고나면 카운트를 해준다.
5. 기존에 내 풀이의 한계는 visited 를 구현하지 않았다는 것이다.

def dfs(node, computers, visited):
    
    print(f'input node : {node}')
    
    visited[node] = True
    for i,x in enumerate(computers[node]):
        if x ==1 and (visited[i] == False):
            # print(i,x)
            print('visit ', i)
            
            dfs(i, computers, visited)


def solution(n, computers):
    visited = [False] * n
    cnt = 0
    
    for i in range(n):
        if visited[i] == False:
            dfs(i,computers,visited)
            cnt = cnt+1

            
    return cnt

네트워크 2

새롭게 풀었다.
1. dfs로 구현
2. 기본적으로 각 노드마다 각자의 연결되지 않은 네트워크를 구성할 가능성이 있다.
따라서 우선 1을 더해주되,
3. 방문 여부를 구분하여 노드가 연결되면 카운트에서 1을 뺀다. ( 연결되면 다른 네트워크에 종속되므로 )

import numpy as np
def solution(n, computers):
    
    graph = {}
    for i, com in enumerate(computers):
        graph[i] = com
        
    visited = [False]*len(computers)
    
    count = 0
    
    def dfs(i, graph, visited): # i : n번 노드, 
        visited[i] = True
        for to_visit,_ in enumerate(graph[i]): # index : to_visit, _ : flag (1/0)
            if visited[to_visit] == False and _==1: # 1로 연결되어 있고 미방문한 노드면 방문
                # visited[to_visit] = True
                print(f'current : {i}, to_visit : {to_visit}')
                nonlocal count
                count = count -1
                dfs(to_visit, graph, visited)
        
    print(graph)
    
    for i,_ in enumerate(computers):
        count = count + 1
        dfs(i,graph, visited)
        
            
    return count

단어 변환

import heapq
from collections import deque

def solution(begin, target, words):
    answer = 0
    visited = [0 for _ in range(len(words))] 
    if target not in words:
        return 0

    """
    helper 함수를 통해, 오직 한 부분만 다른 단어를 찾는다. 
    """
    def compare_helper(aWord,bWord):
        difference=0
        for i in range(len(aWord)):
            if aWord[i] != bWord[i]:
                difference+=1
        if difference ==1:
            return True
        return False



    """
    주의사항. 변환할 수 없는 경우는, 
    1) target word가 아예 리스트에 없다. line6에서 해결 
    2) target word가 있음에도 불구하고, 
    어떠한 경로를 거치더라도 (최대 len(words)겠지) visited가 꽉 찼는데도, 
    current 와 target이 같아지지 않는 경우.
    """
    def bfs(current, words,visited):
        """
        words 중에서 aword(현재 단어)에서 변환이 가능한 조건을 지닌 단어들만을 큐에 추가한다.
        헬퍼 함수의 도움을 받는다.
        """
        queue= deque()
        queue.append((current,0))
        
        # aword : queue
        # 1 : hit, 0
        # 2 : []
        # 3 : hot, 1 
        # 4 : 'dot', 2
        #
        trial = 0
        while queue:
            trial = trial + 1
            aword = queue.popleft()
            if aword[0] == target:
                return aword[1]

            for i in range(len(words)):
                if compare_helper(aword[0], words[i]) and visited[i] ==0:
                    queue.append((words[i],aword[1]+1)) # aword[1] : depth
                    print(trial, words[i], queue)
                    
                    visited[i] = 1
        return 0

    return bfs(begin, words, visited)

1 hot deque([('hot', 1)])
2 dot deque([('dot', 2)])
2 lot deque([('dot', 2), ('lot', 2)])
3 dog deque([('lot', 2), ('dog', 3)])
4 log deque([('dog', 3), ('log', 3)])
5 cog deque([('log', 3), ('cog', 4)])

단어변환2

1.테케 3번 틀리는데, 왜 틀리는지는 몰루?
2.중요한 아이디어로, bfs에서 뎁스?를 관리할 때, 큐를 하나 더 많들어서 뎁스를 관리할 수 있음. 여기선 dist_deq

import heapq
from collections import deque



def solution(begin , target , words ):
    # begin = 'aab'
    # target = 'aba'
    # words = ["abb", "aba"]


    words.append(begin)
    graph = {}
    for word_a in words:
        
        _list = []
        
        for word_b in words:
            count = 0
            for i, _ in enumerate(list(word_a)):
                if word_b[i] == word_a[i]:
                    count = count + 1

            if count == len(word_a)-1:
                # print(word_a, word_b, count)
                _list.append(word_b)
                
        graph[word_a] = _list

    print(graph)
    
    visited = {}
    for word in words:
        visited[word] = False
        
    deq = deque()
    dist_deq = deque()
    count = 0
    


    def bfs(start, target, graph, visited, deq):
        
        
        
        deq.append(start)
        dist_deq.append(0)
        
        flag=False
        
        while flag==False:
            
            print('---------------------')
            print(deq)
            _temp = deq.popleft()   # hit
            current_distance = dist_deq.popleft()
            
            to_visit = graph[_temp] # ['hot']
            
            
            print(f'from {_temp}') # hot
            visited[_temp] = True # hit
            
            
            for node_in_same_depth in list(to_visit): # hot
                print(node_in_same_depth)
                if visited[node_in_same_depth] == False: # and node not in list(deq):
                    print(f'count: {current_distance}, to_visit : ({node_in_same_depth}) in {to_visit}')
                    deq.append(node_in_same_depth)
                    dist_deq.append(current_distance+1)
            
            
            print(deq)
            
            if len(list(deq))==0:
                flag=True
                return 0
            
            if node_in_same_depth == target :
                print(current_distance,'=====')
                flag=True
                return current_distance+1