[백준/boj/알고리즘/파이썬(python)/C++/DFS]#11724:연결요소의 개수

https://www.acmicpc.net/problem/11724

 

11724번: 연결 요소의 개수

그래프이론_너비우선탐색, 깊이우선탐색 BFS DFS 문제

나는 DFS를 이용하여 풀었다. (BFS까지 나중에 풀어봐야지!) 

예제 스캐치 

파이썬 코드에서 계속 시간초과가 나서 그 원인을 보니

input() 이었다. 백준에서는 input()함수가 시간초과가 잘 난다고 하니 참고하시길..!

sys 라이브러리 import해서 입출력하면 해결된다. 

그리고 DFS를 재귀로 풀었는데 여기서 10000으로 재귀 limit을 두어야 시간초과가 안 난다. 

제한을 안 걸면 무제한적으로 재귀가 돌 수 있다고 한다. 

 

queue로 푸는 방식도 가능한 것 같은데, 나는 그냥 재귀로 했다.

queue써서 pop()해서 visited 방문유무 탐색하는 풀이도 가능해보인다. 

시간적 비용은 큐가 더 빠를 것 같다.

파이썬(Python)코드

import sys

sys.setrecursionlimit(10000)


node, edge = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(node+1)]

visited = [False for _ in range(node+1)]

for _ in range(edge): #making graph
    n1, n2 = map(int, sys.stdin.readline().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
    graph[n1].sort()
    graph[n2].sort()

    
def DFS(graph, visited, node):
    visited[node] = True
    for i in graph[node]:
        if not visited[i]:
            DFS(graph,visited,i)



comp = 0


for i in range(1,node+1):
    if visited[i] == False:
        DFS(graph,visited,i)
        comp += 1
        
sys.stdout.write(str(comp))

 

 

c++코드는 위의 파이썬코드를 그대로 문법만 조금 고치면 된다. 

 

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

void DFS(vector<int> *graph, bool *visited, int node){
	visited[node]=true;
	for(int i=0;i<graph[node].size();i++){
		int next = graph[node][i];
		
		if(visited[next]==false){
		
			DFS(graph,visited,next);
		}
	}
}

int main(){
	int node, edge;
	cin>>node>>edge;
	vector<int> graph[node+1];
	
	for(int i=0;i<edge;i++){
		int n1, n2;
		cin>>n1>>n2;
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}
	
	bool visited[node+1]={false};
	int comp = 0;
	for(int i=1;i<=node;i++){
		if(visited[i]==false){
			DFS(graph,visited,i);
			comp += 1;	
		}
	}
	
	cout<<comp;
}