[Problem Solving] BJ_2606. 🦠 바이러스

🧐 문제 분석

한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워트 상에서 연결된 모든 컴퓨터는 바이러스에 걸리게 됨

• [입력]
  첫번째 줄: N (컴퓨터의 수)
  둘째 줄: M (네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수)
  M개 줄: 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍
• [출력]
  1번 컴퓨터가 바이러스에 걸렸을 때, 영향을 받는 컴퓨터의 수

0. 입출력

// 입력
7
6
1 2
2 3
1 5
5 2
5 6
4 7

// 출력
4

1. 문제 접근 방법

• 그래프 문제
  컴퓨터: 노드
  연결 케이블: 간선
• 연결노드 탐색
  연결 순서 상관없음 -> BFS /DFS
  1번 노드를 시작으로 다음 연결된 노드를 갈 때 카운팅

💻 코드 작성

1. BFS

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		// [input]
		int N = Integer.parseInt(br.readLine());
		
		// 그래프 초기화
		List<List<Integer>> graph = new ArrayList<>();
		
		for(int i=0; i<=N+1; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 간선 입력
		int M = Integer.parseInt(br.readLine());
		
		for(int m=0; m<M; m++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v= Integer.parseInt(st.nextToken());
			
			graph.get(u).add(v);
			graph.get(v).add(u);
		}
		
		// bfs 탐색
		Deque<Integer> queue = new ArrayDeque<>();
		boolean[] visited=new boolean[N+1];
		
		queue.offer(1);
		visited[1]= true;
		int count = 0;
	
		while(!queue.isEmpty()) {
			int current=queue.poll();
			for(int el: graph.get(current)) {
				if(!visited[el]) {
					visited[el]=true;
					count ++;
					queue.add(el);
				}
			}
		}
		
		System.out.println(count);
	}// main

2. DFS

public class Main_DFS {
	static List<List<Integer>> graph;
	static boolean[] visited;
	static int count =0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		// [input]
		int N = Integer.parseInt(br.readLine());
		
		// 그래프 초기화
		graph = new ArrayList<>();
		
		for(int i=0; i<=N+1; i++) {
			graph.add(new ArrayList<>());
		}
		
		// visited 배열
		visited = new boolean[N+1];
		
		// 간선 입력
		int M = Integer.parseInt(br.readLine());
		
		for(int m=0; m<M; m++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v= Integer.parseInt(st.nextToken());
			
			graph.get(u).add(v);
			graph.get(v).add(u);
		}
		
		// dfs 탐색
		
		dfs(1);
		
		System.out.println(count-1);
	}// main
	

	
	public static void dfs(int v) {
		
		visited[v]=true;
		++count;
		for(int next:graph.get(v)) {
			if(!visited[next]) {
				dfs(next);
			}
		}
		
	}
}

3.복잡도 & 개선 방향

• 시간복잡도: O(V + E)
  BFS, DFS 모두 그래프의 모든 노드와 간선을 탐색하는 알고리즘

4. 🤯 ??? & !!!

• DFS & BFS
  어떤 알고리즘이 더 적합한가?
  두 알고리즘 모두 시간 복잡도가 O(V + E)로 동일

• DFS 탐색 로직 오류
  DFS 함수에서 for 루프 없이 첫 번째 연결된 노드만 탐색하는 실수

• 결과 카운트 오류
  시작점인 1번 컴퓨터를 포함하여 카운팅해서 최종 결과가 1만큼 크게 나오는 실수