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

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

https://www.acmicpc.net/problem/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 #include using namespace std; int cnt=0; void DFS(vector *graph, bool *visited, int node){ visited[node]=true; for(int i=0;i>node>>C; vector graph[node+1]; for(int i=0;i>n1>>n2; graph[n1].push_back(n2); graph[n2].push_back(n1); } bool visited[node+1]={false}; DFS(graph,visited,1); cout<

from http://hidemasa.tistory.com/95 by ccl(A) rewrite - 2021-09-05 13:26:31