본문 바로가기
728x90
반응형

DFS

로봇공학 정리 - 2(Robot Motion Planning [BFS, DFS, A*, DP], Path Smoothing, PID)
Computer Science/기타 2022. 11. 3. 로봇공학 정리 - 2(Robot Motion Planning [BFS, DFS, A*, DP], Path Smoothing, PID) Robot의 Motion Planning의 가장 큰 목표는 다음과 같다. 항상 최적의 path를 찾아야 하고, 최적의 path란 최단경로와 최소비용을 만족하는 것이다. BFS) 너비 우선 탐색(Queue(FIFO)), 최단거리 보장 DFS) 깊이 우선 탐색(Stack(LIFO), 재귀), 최단거리 보장 x DFS와 BFS는 올해 초에 블로그에 정리한 적이 있다. https://geek-inside.tistory.com/entry/DFS DFS & BFS DFS와 BFS를 공부하기 앞서 큐와 스택에 대해서 간단하게 정리해봤다. 아래는 DFS에 관한 정리 및 구현 코드 이다. 재귀함수를 사용하는 것이 특징이다. 코드와 정리한 그림을 연결지어 생각하면 geek-inside.tistory.com A* 알고리즘)..
Algorithm & Data Structure 2022. 7. 23. 백준 - 9466번(DFS, cycle 생성) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net import sys sys.setrecursionlimit(111111) def dfs(x): global result visited[x] = True cycle.append(x) if visited[arr[x]] == True: for i in range(len(cycle)): if arr[x] == cycle[i]: result = result - (len(cycle) - i) break retur..
Algorithm & Data Structure 2022. 4. 9. 백준 - 2178번(BFS) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) arr = [] for _ in range(n): arr.append(list(map(int, sys.stdin.readline().rstrip()))) def BFS(): # 상,하,좌,우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] q = deque..
728x90
반응형

티스토리툴바