반응형 BFS2 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 깊이 우선 탐색 (DFS : Depth First Search) 대표적으로 백트래킹에 사용한다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. 자동 미로 생성에 많이 사용 되는 알고리즘! 장점 현 경로상의 노드만 기억하면 돼서 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. ( 임의 깊이까지만 탐색하도록 만들기! ) 얻어진 해가 최단 경로가 아닐 수도 있다. 왜냐? DFS는 일단 해를 찾으면 탐색이 끝나기 때문이다. 동작 방식 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 .. 2022. 2. 1. 백준 15649 : N과 M (1) (파이썬) N과 M (1)https://www.acmicpc.net/problem/15649코드1# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/import itertoolsn, m = map(int,input().split())nums = [i+1 for i in range(n)]for ln in list(itertools.permutations(nums,m)): for i in range(m): print(ln[i],end= ' ') print('')코드 2# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/def bts(n, m, visite.. 2022. 2. 1. 이전 1 다음 반응형
