dfs

11724번: 연결 요소의 개수첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주www.acmicpc.net문제 보기 ↓더보기더보기더보기더보기문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어..

DFS란?DFS(깊이 우선 탐색)는 그래프의 시작 노드에서 출발하여 탐색할 할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘DFS의 특징?스택 자료구조를 사용하지만 보통은 스택 성질을 가지는 재귀 함수로 구현한다.재귀함수를 이용하기 때문에 스택 오버플로(시간초과)에 유의해야한다. -> 다음 게시글에 설명할 BFS보다 느리다.한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열 필요DFS의 동작과정1. DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화인접 리스트 그래프로 표현하기방문 배열 초기화하기시작 노드 스택에 삽입하기2. 스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입pop을 수행해 스택에서 노드를 ..