dfs

개요백준의 1012번 문제를 풀어봅시다, 문제는 다 알고 계시겠지만 링크는 아래와 같습니다https://www.acmicpc.net/problem/1012요약하자면 x,y로 된 배추 밭에 값이 1로 묶인 묶음 하나당 배추흰지렁이가 한마리가 필요하다면 전체 밭에서 필요한 배추흰지렁이의 최소 수는?조건에 묶음이란 상하좌우가 이어진게 한 묶음으로 봅니다 즉 아래 그림은 총 5마리가 필요한 걸 알 수 있습니다.  다가가기처음에 문제를 보고 가장 먼저 떠오른 생각은 왼쪽 위 부터 차례대로 오른쪽 아래로 내려오니깐현재 좌표에서 오른쪽, 아래 값만을 체크하면서 내려오면 되지 않을까라는 생각을 가장 먼저 해봤는데 아래와 같은 배추 밭에서는 에서는 아래 처럼 왼쪽와 아래에 1이 있을 경우 소거법으로 진행할 경우 성공적으..

개요 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 (Depth-First Search), 깊이 우선 탐색 그래프의 모든 정점을 탐색하는 방법으로 최대한 깊이 탐색을 한 후 더 이상 깊이 들어가지 못한다면 이전으로 돌아와 다른 진행 방향으로 깊이 탐색을 진행합니다. 노드들을 돌며 순서를 스택(재귀)에 쌓는 방식을 사용합니다. 아래처럼 끝까지 가보..