백준 11724 연결요소의 개수 파이썬, C++

리뷰

DFS로 풀었다, 파이썬 첫 시도는 재귀가 너무 깊어서 RecursionError, 이후는 sys를 사용하지 않아 시간초과

sys를 사용하니 문제 풀이가 되었다, 확실히 파이썬과 C++ 성능차이가 큰 것 같다.

 

문제 풀이 

1. 1에서 n까지 딕셔너리의 key로 설정하고 value는 빈 리스트로 초기화 해준다.
2. m줄에 걸쳐 들어오는 간선을 딕셔너리에서 양방향으로 각 key의 리스트에 추가해준다.
3. 방문을 체크할 리스트를 False로 n + 1의 길이만큼 초기화 해준다.
4. 1에서 n까지 for문을 돌며 아직 방문하지 않은 인덱스라면 dfs를 돌려주고 연결 요소를 1만큼 더해준다.
5. 총 연결 요소를 출력해 준다.

 

참고 사항

파이썬을 사용할 거라면 sys.stdin.readline()을 사용해 주면 시간 초과를 피할 수 있다.

재귀 깊이 오류를 피하려면 스택을 써주면 된다.

 

정답 코드

파이썬 코드

import sys

n, m = map(int, sys.stdin.readline().split())
dic = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    dic[a].append(b)
    dic[b].append(a)
v = [False] * (n + 1)


def dfs(index):
    stack = [index]
    while stack:
        key = stack.pop()
        if not v[key]:
            v[key] = True
            for val in dic[key]:
                if not v[val]:
                    stack.append(val)


ans = 0
for i in range(1, n + 1):
    if not v[i]:
        dfs(i)
        ans += 1
print(ans)

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int n, m;
map<int, vector<int>> dic;
vector<bool> v;

void dfs(int index) {
	vector<int> stack;
	stack.push_back(index);
	while (stack.size()) {
		int node = stack.back();
		stack.pop_back();
		if (!v[node]) {
			v[node] = true;
			for (int i = 0; i < dic[node].size(); i++) {
				if (!v[dic[node][i]]) stack.push_back(dic[node][i]);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		dic[a].push_back(b);
		dic[b].push_back(a);
	}
	int cnt = 0;
	v.resize(n + 1, false);
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			dfs(i);
			cnt++;
		}
	}
	cout << cnt;
}