dfs
백준 2178: 미로탐색 해설- python
✏️ 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 풀이 미로에서 최단거리를 구하는 문제다. 최단거리를 구하는 탐색문제의 경우 BFS가 적합하다. from collections import deque n,m=map(int,input().split()) matrix=[] for _ in range(n): matrix.append(list(map(int,input()))) dx=[-1,1,0,0] dy=[0,0,1,-1] def bfs(a,b): queue=deque([[a,b]]) while(queue): x,y=queue.pop..
DFS와 BFS 각각 사용하는 경우
✏️ DFS와 BFS의 구현방법과 차이 설명 아래글에 설명해두었으니 이 내용은 여기서 확인바란다. 백준 1260: DFS와 BFS 해설- python ✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에.. duckracoon.tistory.com ✏️ DFS와 BFS 각각 어떤 상황에서 사용할까? 어떤 문제를 풀때 DFS를 써야할지, 어떤 문제를 풀때 BFS를 쓸지 난감한 경험때문에 정리한다. When is it practical to use Depth-First Search (DFS) vs..
백준 1260: DFS와 BFS 해설 (파이썬, node.js)
✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ✏️ DFS와 BFS 개념 DFS와 BFS 개념부터가 가물가물해서 처음부터 정리하려고한다. DFS(Depth-First-Search, 깊이우선탐색) 그림이 좋길래 가져와봤다. 탐색순서: 1->2->4->8->5->3->6->7 (1) 탐색시작노드를 스택에 삽입하고 방문처리를 한다. (2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있..