[백준/BOJ/알고리즘/DFS/그래프/파이썬(python)/C++]#2606_바이러스

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

2606번: 바이러스

그래프 이론(DFS/BFS)로 간단하지만 반례 때문에 좀 애를 먹었다.

root를 빼고 계산해야한다. 

트리처럼 상위하위노드는 고려안해도 그래프로 간단하게 풀 수 있는 문제다.

 

원래는 for문을 main에서 돌리고 DFS함수에서도 for문을 또 돌려서 visited를 확인했는데, 그러니 반례와 자꾸 답이 다르게 나와서 for문을 지우고 노드1로 DFS를 호출해서 거기서만 for문을 돌리니 오류가 없었다.

예제와 반례가 계속 1이 계속 차이가 나서 디버깅을 계속 해봤는데 

어디선가 한번 더 count가 되는지는 모르겠지만 계속 있는 것 같다.

 

로직을 최대한 단순화 시키는게 좋은 것 같다.

 

파이썬 코드

import sys
input = sys.stdin.readline

node = int(input())
graph = [[0] for _ in range(node+1)]
visited = [0 for _ in range(node+1)]
C = int(input())

for i in range(C):#making graph
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

cnt=0  
def DFS(graph, visited, node):
    visited[node] = 1
    global cnt
    for i in graph[node]:
        if visited[i]==0:
            DFS(graph, visited, i)
            cnt+=1

DFS(graph, visited, 1)

print(cnt-1)

C++코드

#include<iostream>
#include<vector>
using namespace std;
int cnt=0;
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);
			cnt+=1;
		}	
	}
}
int main(){
	int node, C;
	cin>>node>>C;
	vector<int> graph[node+1];
	
	for(int i=0;i<C;i++){
		int n1, n2;
		cin>>n1>>n2;
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}
	
	bool visited[node+1]={false};
	DFS(graph,visited,1);
	
	cout<<cnt;
	
}