깊이/너비 우선탐색 참고 URL
A - B - C - H - D - I - J - M - E - G - K - F - L
A - B- C - D - E - F - G - H - I - J - K - L - M
1번 방식은 한 단계씩 나아가면서 해당 노드와 같은 레벨에 있는 노드들(즉, 형제 노드들)을 먼저 순회하는 방식이다.
이러한 방식을 Breath First Search (너비 우선 탐색, BFS) 라고 한다.
2번 방식은 한 노드의 자식을 타고 끝까지 순회한 다음에, 다시 돌아와서 다른 형제의 자식을 타고 내려가며 순회하는 방식이다.
이러한 방식은 Depth First Search (깊이 우선 탐색, DFS) 라고 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 graph = { 'A' : ['B' ], 'B' : ['A' , 'C' , 'H' ], 'C' : ['B' , 'D' ], 'D' : ['C' , 'E' , 'G' ], 'E' : ['D' , 'F' ], 'F' : ['E' ], 'G' : ['D' ], 'H' : ['B' , 'I' , 'J' , 'M' ], 'I' : ['H' ], 'J' : ['H' , 'K' ], 'K' : ['J' , 'L' ], 'L' : ['K' ], 'M' : ['H' ] }
BFS (Python) 1 2 3 4 5 6 7 8 9 10 11 12 13 def bfs (graph, start_node ): visit = list () queue = list () queue.append(start_node) while queue: node = queue.pop(0 ) if node not in visit: visit.append(node) queue.extend(graph[node]) return visit
DFS (Python) 1 2 3 4 5 6 7 8 9 10 11 12 13 def dfs (graph, start_node ): visit = list () stack = list () stack.append(start_node) while stack: node = stack.pop() if node not in visit: visit.append(node) stack.extend(graph[node]) return visit
cf) append() vs extend()
1 2 3 4 5 6 x = ["my" , "name" , "is" ] y = ["kim" , "hyun" , "soo" ] x.append(y) x.extend(y)
1 2 3 4 5 6 7 8 9 10 11 def solution (numbers, target ): tree = [0 ] for num in numbers: sub_tree = [] for tree_num in tree: sub_tree.append(tree_num + num) sub_tree.append(tree_num - num) tree = sub_tree return tree.count(target)
그래프의 깊이 만큼 더한 값을 리스트에 저장 후 해당 합이 target값과 같다면 count 한다.
1 2 3 4 5 6 7 8 9 numbers = [1 , 1 , 1 , 1 , 1 ] target = 3
1차 답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def solution (n, computers ): netStat = [0 ] * n i = -1 for computer in computers: i += 1 j = -1 for net in computer: j += 1 if j != i and net == 1 : netStat[j] = 1 return netStat.count(0 ) + 1
테스트 케이스 4, 5, 7 실패
1 2 3 n = 5 computers = [[1 , 1 , 0 , 0 , 0 ], [1 , 1 , 0 , 0 , 0 ],[0 , 0 , 1 , 0 , 1 ], [0 , 0 , 0 , 1 , 0 ], [0 , 0 , 1 , 0 , 1 ]]
해당 경우 [A, B] , [C, E], [D] 3개의 네트워크가 생성되지만 return 값은 2로 결과가 다르게 나옵니다.
다른 사람 답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def solution (n, computers ): answer = 0 visit = [0 for _ in range (n)] def dfs (start ): st = [start] while st: com_num = st.pop() if visit[com_num] == 0 : visit[com_num] = 1 for i in range (len (computers[0 ])): if computers[com_num][i] == 1 and visit[i] == 0 : st.append(i) i = 0 while 0 in visit: if visit[i] == 0 : dfs(i) answer += 1 i += 1 return answer
DFS/BFS의 개념에 대해 이해하지 않고 문제만 풀다보니 계속 잘못된 풀이로 이어졌다.
DFS/BFS를 이용하지 않고 해당 문제를 풀어보려 했지만 시간상 너무 오래걸려 해당 문제를 해결하지 못하고 DFS/BFS 개념 정리 후 해당 답안을 참고해 문제를 풀었다.
1차답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 def solution (begin, target, words ): visited = [0 ] * len (words) if target not in words: return 0 answer = 0 sm_idx = 0 stack = [begin] while stack: st = stack.pop() if begin == target: return answer idx = - 1 break_idx = False for word in words: if break_idx == True : break idx += 1 sm_idx = 0 tg_idx = 0 for i in range (len (begin)): if target[i] == st[i]: tg_idx += 1 if word[i] == st[i]: sm_idx += 1 if tg_idx == len (word) - 1 : answer += 1 return answer elif sm_idx == len (word) - 1 and visited[idx] == 0 : visited[idx] = 1 stack.append(word) answer += 1 break_idx = True break return answer
테스트 케이스 1번 통과 불가
2차 답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 answer = 0 def dfs (begin,target,words,visited ): global answer stacks = [begin] while stacks: stack = stacks.pop() if stack == target: return answer for w in range (0 ,len (words)): if len ([i for i in range (0 ,len (words[w])) if words[w][i]!=stack[i]]) == 1 : if visited[w] != 0 : continue visited[w] = 1 stacks.append(words[w]) print (stack) answer +=1 def solution (begin, target, words ): global answer if target not in words: return 0 visited = [0 for i in words] dfs(begin,target,words,visited) return answer
1차답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 def dfs (tickets, begin, visited ): answer = [begin] stack = [begin] while (stack): st = stack.pop() idx = -1 for ticket in tickets: idx += 1 if ticket[0 ] == st and visited[idx] == 0 : visited[idx] = 1 stack.append(ticket[1 ]) answer.append(ticket[1 ]) break return answer def solution (tickets ): tickets.sort(key= lambda x: x[1 ]) visited = [0 ] * len (tickets) begin = "ICN" answer = dfs(tickets, begin, visited) return answer
테스트 1 ,테스트 2 통과불가
case : [[ICN, A], [A, C], [A, D], [D, B], [B, A]]
*** [INC, A, C] 가 되버리면 해당 경로가 끊기기 때문에 다음 경로가 있는지 판단하는 조건을 생각해야한다.***
2차 답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def dfs (tickets, begin, visited, plist ): answer = [begin] stack = [begin] while (stack): st = stack.pop() idx = -1 for ticket in tickets: idx += 1 if ticket[0 ] == st and visited[idx] == 0 : if sum (visited) != len (visited) and ticket[1 ] in plist: visited[idx] = 1 stack.append(ticket[1 ]) answer.append(ticket[1 ]) break elif sum (visited) == len (visited) -1 : stack.append(ticket[1 ]) answer.append(ticket[1 ]) break return answer def solution (tickets ): tickets.sort(key= lambda x: x[1 ]) visited = [0 ] * len (tickets) begin = "ICN" plist = list (map (lambda x: x[0 ] , tickets)) answer = dfs(tickets, begin, visited, plist) return answer
테스트 1 통과 불가
tickets = [[“ICN”, “COO”], [“ICN”, “BOO”], [“COO”, “ICN”], [“BOO”, “DOO”]]
*** 모든 요소를 사용하지 않고 [ICN, ,BOO] 리턴***
3차 답안 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution (tickets ): answer = [] def dfs (start,ticList,path ): path.append(start) if len (ticList)==1 : path.append(ticList[0 ][1 ]) answer.append(path) return for t in ticList: if t[0 ]==start: ticList_copy = ticList.copy() ticList_copy.remove(t) dfs(t[1 ],ticList_copy,path.copy()) dfs("ICN" ,tickets,[]) return min (answer)
