바이러스(DFS)_백준_2606

-문제-

 

-문제 접근-

1번 컴퓨터로부터 감염되는 컴퓨터 수를 구하는 문제의  DFS(깊이 우선 탐색) 문제입니다.

 

• N: 컴퓨터의 수 (1번 ~ N번)
• M: 네트워크 연결 수 (간선 개수)
• network: 각 노드(컴퓨터)에 연결된 다른 노드(컴퓨터)의 목록
• visited: 방문 여부(감염 여부) 체크
• icom: 감염된 컴퓨터 개수(1번 컴퓨터 제외)

 

 

-전체 코드-

 

push_back(): 벡터의 뒤(back) 쪽에 새로운 원소를 추가할 때 사용합니다.

 

dfs 함수:

 

-visited[cur] = true;

현재 노드(cur)가 방문(감염) 되었다고 표시

 

-인접 리스트(network[cur])로 연결된 모든 노드(next) 확인

 

-감염되지 않은(!visited[next]) 노드 발견 시: icom++ (새롭게 감염되는 컴퓨터 1대 증가), dfs(next) (재귀로 감염 확산)