DFS (Depth First Search, 깊이 우선 탐색)
DFS (Depth First Search, 깊이 우선 탐색) 시작 정점으로부터 연결 된 노드를 따라 마지막 노드까지 탐색하는 알고리즘 특징 - 모든 노드를 탐색해야할 때 사용 - 재귀적 장점 - 구현이 BFS보다 간단하다. - 저장 공간이 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 단순 검색 속도가 BFS보다 느리다. - 목표까지의 경로가 여러 개인 경우 구한 해가 최적이 아닐 수 있다. - 해가 없는 경로에 깊이 빠질 가능성이 있다. -> 임의의 깊이까지 탐색할 때까지 목표를 찾지 못한다면 다음 경로를 찾을 수도.. Python 구현 코드 check = [0 for i in range(N)] # 방문 여부를 확인 s = [[0, 1, 1, 1], [1, ..
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys, copy sys.setrecursionlimit(100000) N = int(sys.stdin.readline()) s = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] for i in range(N): h = max(s[i]) result = 1 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] def dfs..