sm 기술 블로그

N,M = map(int, input().split()) visited = [False] * N tmp = [] def DFS(N,M,depth): if depth == M: print(' '.join(map(str,tmp))) return for i in range(N): if not visited[i]: visited[i] = True tmp.append(i + 1) DFS(N, M, depth + 1) visited[i] = False tmp.pop() DFS(N,M,0) 문제요약 DFS를 이용하여 백트래킹을 해보아라. 설명 DFS와 백트래킹에 대한 개념은 아래를 참고하자. https://smhope.tistory.com/309 백트래킹 백트래킹 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복..

백트래킹 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정 모든 경우의 수를 전부 고려하는 알고리즘이다. 트리 탐색 알고리즘이라고 봐도 무방하며 방식에 따라 깊이우선탐색 (Depth First Search - DFS) 와 최선 우선 탐색 (Best First Search - BFS) 가 있다. 모든 경우의 수를 고려해야 한다면 DFS가 좋으며 BFS로도 구현이 가능하나 큐의 크기, 속도가 똑같아 DFS가 좋다. 장점 무한히 깊은 곳을 찾아야할때 효과적이다. 단점 모든곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수 있다. https://smhope.tistory.com/308 너비 우선 탐색(BFS) 너비 우선 탐색(BFS) 루트 노드에서 시작해서 인접한..

너비 우선 탐색(BFS) => 큐 사용 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 가장 가까운 정점을 먼저 방문하고 이후 멀리 떨어져 있는 정점을 방문하는 방식이다. 특징 직관적이지 않다. 큐를 사용한다. (선입 선출이 원칙이다) Prim, Dijkstra 알고리즘과 유사하다. 과정 결국 이동 순서는 0 -> 1 0 -> 2 0 -> 4 1 -> 2 2 -> 3 3 -> 4 이 된다. 시간 복잡도 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2)

깊이 우선 탐색(DFS) -> 스택 사용 (재귀 이용 -> 재귀 자체가 스택임) 루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 깊이 우선 탐색(DFS) 에 비해서 너비 우선 탐색(BFS)이 보다 좀 더 간단하다. 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 과정 결국 이동 순서는 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 다음과 같다. 시간 복잡도 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2)