DFS
-
[Data Structure] DFS vs BFS with PythonData Structure 2022. 2. 23. 00:41
아래 글을 보고 공부한 후 정리, 번역한 글입니다. Reference https://medium.com/nothingaholic/depth-first-search-vs-breadth-first-search-in-python-81521caa8f44 Depth-First Search vs. Breadth-First Search in Python The simplified explanation of the two traversals algorithm. medium.com 1. Tree traversal 트리 순회는 노드를 반복하지 않고 정확히 한 번 각 노드를 checking(visiting)하거나 업데이트하는 것으로 알려져 있음 모든 노드는 간선을 통해 연결되어 있기 때문에 항상 root 노드부터 시작함 =..
-
[백준] 2606번 바이러스 (python 파이썬)Coding Test/백준 2022. 2. 16. 23:42
깊이우선탐색(dfs)로 해결 n_computer = int(input()) # 컴퓨터의 수 n_connection = int(input()) # 연결의 수 # 빈 인접 행렬 생성 # 노드가 1부터 시작하므로 인덱스가 0인 경우 무시하고 1부터 시작하기 위해 +1 해줌 graph = [[] for _ in range(n_computer+1)] # 연결된 컴퓨터의 번호 쌍 입력 받기 for i in range(n_connection): idx, val = map(int, input().split()) # 인접 행렬 생성 graph[idx].append(val) graph[val].append(idx) visited = [False]*(n_computer+1) def dfs(visited, v, graph):..
-
[백준] 2667번 단지번호붙이기 (python 파이썬)Coding Test/백준 2022. 2. 16. 23:32
2667번: 단지번호붙이기 깊이우선탐색(dfs)로 해결 N = int(input()) # 지도의 크기 N 입력 받기 graph = [] for i in range(N): graph.append(list(map(int, input()))) # 0 or 1 입력 받기 # dfs 함수 정의하는 부분 # return은 [단지 내 아파트의 개수, 단지의 경우 True 반환] def dfs(x, y, li): # 지도 범위를 벗어나면 안 되므로 if x=N or y=N: return [0, False] # 1인 경우 아파트이므로 방문 if graph[x][y]==1: # 여기서 li는 단지 내 아파트의 개수를 구하기 위해 사용됨 li.append(1) # 아파트에 방문했으므로 li 리스트에 1을 저장 graph[x..
-
기초 자료 구조Data Structure 2022. 2. 6. 19:28
Reference 이것이 코딩 테스트다 with 파이썬 스택 선입후출, 후입선출 stack = [] stack.append(3) # 3 stack.append(5) # 3 5 stack.append(7) # 3 5 7 stack.pop() # 3 5 stack.append(4) # 3 5 4 stack.pop() # 3 5 큐 선입선출 재귀 함수 자기 자신을 다시 호출하는 함수 factorial 계산할 때 Graph 그래프는 노드(Node), 간선(Edge) 이 때 노드를 정점(Vertex)라고도 함 두 노드가 간선으로 연결되어 있다면 '두 노드는 입접하다(adgacent)'라고 표현 프로그래밍에서 그래프틑 크게 2가지 방식으로 표현할 수 있음 인접 행렬(adjacency matrix): 2차원 배열로 ..