본문 바로가기

DFS

 (3)
DFS 관련 연산 문제 DFS 관련 연산 문제 DFS def dfs(파라미터 값): if 종료조건: 출력해야할 파라미터값(없으면 생략) return # 계속 탐색 else: dfs(파라미터값) 📝 파라미터 값 현재 탐색위치 탐색 조건 탐색 후, 출력해야 하는 결과값 탐색 대상 📝 종료 조건 매우 중요한 설정! 언제까지 탐색할 껀지!! 📝 프로그래머스, 타겟넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # -------------------- dfs 풀이 ---..
백준 1260번 DFS, BFS 백준 1260번 DFS, BFS ✏️ BOJ 1260 ✏️ DFS : 하나의 노드만 몰아서 본다. 몰아서 탐색! 1. start_node를 방문, visited 배열에 방문 기록 남기기 2. start_node의 인접 노드 방문(current_node), visited배열에 방문 기록 남기기 3. 인접노드의 방문 기록이 있거나, 인접노드가 없으면 직전 노드로 돌아간다. 4. 모든 노드를 방문했다면, 더 이상 방문할 노드가 없으므로 탐색 종료 def dfs(c): # current node ans_dfs.append(c) # 방문 노드 추가 visited[c] = 1 # 방문 표시 for n in adj[c]: if not visited[n]: # 방문하지 않은 노드의 경우 dfs(n) ✏️ BFS : 여..
자료구조 4주차 _ DFS & BFS 자료구조 4주차 _ DFS & BFS 📌 DFS란? Dep First Search 인접한 노드를 끝까지 탐색 끝까지 파고드는 것이라, 그래프 최대 깊이 만큼의 공간을 요구 공간↓ 최단 경로 탐색 어려움 📌 BFS란? Breadth First Search 한 노드를 시작으로 인접한 모든 정점들을 다 둘러보는 방식 모든 분기되는 수를 다 저장함. 공간↑ 최단 경로 쉽게 찾을 수 있음 모든 경우의 수를 다 탐색해야하는 경우가 있음. 📌 DFS 재귀함수 구현해보기 # 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, ..

티스토리툴바