문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
예제 입력 1
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1
2
예제 입력 2
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
예제 출력 2
1
DFS를 스택으로 하는 방법도 다시 외워야하는데 너무 잠와서 미루기로 했다. 그래서 지금은 DFS를 이용해 짜보기로 했다. 지금 현재는 이렇다 2가 출력되어야하는데 5가 출력되길래 무슨 일인가 싶어서 i를 다 찍어보았다. 3 4 0 굉장히 말도 안되는 값을 뿜어내고 있었다. 이렇게 안되는데 이유는 코드 아래에 적어보겠다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int visited[1001];
int map[1001][1001];
int dfs(int n) {
visited[n] = 1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (visited[i] != 1 && map[n][i] == 1) {
dfs(i);
cout << i << ' ';
}
}
return cnt;
}
int main() {
int n, m;
cin >> n >> m;
int u, v;
for (int i = 0; i < m;i++) {
cin >> u >> v;
map[u][v] = 1;
map[v][u] = 1;
}
int res = dfs(v);
cout << res << '\n';
}이 문제는 지금 연결된 게 몇 개인지 찾는 과정이다. 그 과정에서 알고리즘을 이따위로 짜버리면 연결했든 안 했든 일단 탐색을 하게 된다. 그렇기 때문에 이런 식으로 짜면 어떤 노드가 있는지 출력하게 되는 것이다. 그래서 5가 출력이 되었던 거고. 그래서 다시 생각을 해봤는데 vistied를 스위치처럼 생각하고 false → true → false가 될 때 +1을 하는 게 어떤가 싶다. 아니면 재귀를 돌릴 때마다 정한다던지
20241127
DFS(재귀 사용) 방법을 결국 남의 풀이를 보고 알게 됐다. for문의 범위가 잘못 되어 있었고, 결된 정점들을 모두 탐색해야 하지만, 여기함수 내부에서는 n이 현재 정점으로 사용되고 있어 문제가 발생했다. 아래는 수정된 코드다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int visited[1001];
int map[1001][1001];
void dfs(int node, const vector<vector<int>>& map, vector<int>& visited) {
visited[node] = 1;
for (int i = 1; i < map.size(); i++) {
if (!visited[i] && map[node][i] == 1) {
dfs(i, map, visited);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> map(n + 1, vector<int>(n + 1, 0));
vector<int> visited(n + 1, 0);
for (int i = 0; i < m;i++) {
int u, v;
cin >> u >> v;
map[u][v] = 1;
map[v][u] = 1;
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, map, visited);
cnt++;
}
}
cout << cnt << '\n';
return 0;
}
저번에 말한대로 stack으로 하는 방법도 찾아봤다. 변수도 줄고 간단해진 것을 알 수 있었다. 오늘 안에 외워서 순열 사이클에 써먹어야겠다. 이 방법에 더 익숙해져야한다. 오늘 풀어야하는 순열 사이클에서 써먹을 수 있도록. (BFS 사용하는 거면 어떡하지?)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
int dfs(int n, const vector<vector<int>>& map) {
vector<int> visited(n + 1, 0);
stack<int> st;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (visited[i]) continue;
cnt++;
st.push(i);
while (!st.empty()) {
int node = st.top();
st.pop();
if (visited[node]) continue;
visited[node] = 1;
for (int i = 1; i <= n; i++) {
if (!visited[i] && map[node][i] == 1)
st.push(i);
}
}
}
return cnt;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> map(n + 1, vector<int>(n + 1, 0));
//vector<int> visited(n + 1, 0);
for (int i = 0;i < m; i++) {
int u, v;
cin >> u >> v;
map[u][v] = 1;
map[v][u] = 1;
}
cout << dfs(n, map) << '\n';
return 0;
}시작점: i = 1
- 초기 스택 상태:
- st.push(1) → 스택: [1]
- 탐색 1단계 (node = 1)
- st.pop() → node = 1, 스택: []
- 방문 처리: visited[1] = 1
- node = 1과 연결된 노드 2, 5를 스택에 추가.
- st.push(2) → 스택: [2]
- st.push(5) → 스택: [2, 5]
- 탐색 2단계 (node = 5)
- st.pop() → node = 5, 스택: [2]
- 방문 처리: visited[5] = 1
- node = 5와 연결된 노드 1, 2는 이미 방문했으므로 추가하지 않음.
- 탐색 3단계 (node = 2)
- st.pop() → node = 2, 스택: []
- 방문 처리: visited[2] = 1
- node = 2와 연결된 노드 1, 5는 이미 방문했으므로 추가하지 않음.
결과:
- 연결 요소 탐색 완료: 정점 1, 2, 5 방문.
다음 시작점: i = 3
- 초기 스택 상태:
- st.push(3) → 스택: [3]
- 탐색 1단계 (node = 3)
- st.pop() → node = 3, 스택: []
- 방문 처리: visited[3] = 1
- node = 3과 연결된 노드 4를 스택에 추가:
- st.push(4) → 스택: [4]
- 탐색 2단계 (node = 4)
- st.pop() → node = 4, 스택: []
- 방문 처리: visited[4] = 1
- node = 4과 연결된 노드 3, 6 중 6을 스택에 추가:
- st.push(6) → 스택: [6]
- 탐색 3단계 (node = 6)
- st.pop() → node = 6, 스택: []
- 방문 처리: visited[6] = 1
- node = 6과 연결된 노드 3, 4는 이미 방문했으므로 추가하지 않음.
결과:
- 연결 요소 탐색 완료: 정점 3, 4, 6 방문.
+)오늘 구름 알고리즘 스터디를 하다가 알게된건데 JAVA에서 스택은 이전 버전 하위 호환형으로 남겨진거라 쓰지 말라고 하셨다. ArrayDequq가 성능이 빠르다고 하셔서 이거 써야할 거 같다.