백준 : 바이러스 2606 (DFS)

가장 기본적인 DFS 문제인것 같습니다.

 

카운트, 무방향 간선, 인덱스 확인 이렇게 3가지 정도면 잘 확인하면 풀 수 있는 문제입니다.

 

import java.util.*;

public class Main {
	
	static int n,m;
	static boolean[] visited; //노드 수 만큼생성
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	static int result = 0;
	
	public static void dfs(int now) { // DFS(재귀)
		visited[now] = true; //방문표시
		
		for(int i =0; i< graph.get(now).size(); i++) {
			int tmp = graph.get(now).get(i);
			
			if(visited[tmp] == false) { //방문전이라면
				result ++; //카운트 증가
				dfs(tmp); //재귀
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine(); //버퍼
		
		visited = new boolean[n+1]; //인덱스 1부터 시작(0부터 시작인지 1부터 시작인지 주의)***
		
		//그래프 초기화
		for(int i=0; i<n+1; i++) { //그래프 생성
			graph.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<m; i++) { //그래프 생성
			String st = sc.nextLine();
			String[] stArr = st.split(" ");
			
			int a = Integer.parseInt(stArr[0]);
			int b = Integer.parseInt(stArr[1]);
			
			graph.get(a).add(b); //무방향간선인지 아닌지 주의***
			graph.get(b).add(a);
		}
		
		dfs(1); //1번컴퓨터
		
		System.out.println(result);
	
	}
}