[백준 2606] 바이러스

문제

 

풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        
		int point = scan.nextInt();
		int line = scan.nextInt();
		
		int[][] arr = new int[point+1][point+1]; // 그래프 생성
		
		for (int i = 0; i < line; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
		List<Integer> visitedList = new ArrayList<Integer>();
		visit(1, arr, visitedList);
//		for (int i = 0; i < visitedList.size(); i++) {
//			System.out.println(visitedList.get(i));
//		}
		
		System.out.print(visitedList.size() - 1);
		
	}
	
	public static void visit(int start, int[][] arr, List<Integer> visitedList) {
		visitedList.add(start);
		
		for (int i = 1; i < arr.length; i++) {
			if (!visitedList.contains(i) && arr[start][i] == 1) {
				visit(i, arr, visitedList);
			}
		}
	}

}

• DFS, BFS 기초문제
• DFS를 이용하여 인접되어있는 모든 노드를 visitedList 에 추가한다.
• 탐색을 마친 후, list에 들어가있는(기준 노드와 연결되어있는 모든 노드 리스트)의 사이즈를 리턴한다.
• 이때, 기준(1) 은 제외한 나머지 노드의 수만 리턴해야 하므로 -1한다.

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