https://www.acmicpc.net/problem/11724
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
- 접근 방법, 논리 흐름(알고리즘)
스터디에서 간략하게 알고리즘 토론을 한 문제여서 어떻게 접근할 지는 명확했다.
각 노드들을 한번씩 dfs를 돌리고 방문처리 해주는데, 만약 들린 노드가 방문하지 않은 상태라면 그 노드는 다른 요소인 것이다.
왜냐하면 연결된 노드는 첫 dfs를 돌린 노드를 통해 방문 처리가 되었을 것이다.
이를 코드를 짜보면
전의 문제들에서도 많이 접했던 기본적인 dfs 알고리즘에
모든 노드들 각각 한번씩 dfs를 돌려주고 조건(방문처리 되지 않은 노드)에 만족하면 카운트 해주면
카운트가 답이 된다.
'백준 문제풀이' 카테고리의 다른 글
| [백준(BOJ)/C++] 1918번: 후위 표기식 - 코딩밥상 (0) | 2022.12.29 |
|---|---|
| [백준(BOJ)/C++] 13335번: 트럭 - 코딩밥상 (2) | 2022.12.19 |
| [백준(BOJ)/C++] 2178번: 미로 탐색 - 코딩밥상 (0) | 2022.08.24 |
| [백준(BOJ)/C++] 1260번: DFS와 BFS - 코딩밥상 (0) | 2022.08.24 |
| [백준(BOJ)/C++] 1932번: 정수 삼각형 - 코딩밥상 (0) | 2022.08.16 |
