고민의 흔적

백준 2606번 바이러스

내가 떠올린 풀이 해설

어제 풀었던 연결 요소의 개수 문제를 응용해서 풀면 된다. 어제 문제는 DFS 총 수행 횟수를 구하는 문제였지만 오늘 하나의 기준점에서 DFS가 몇 번 수행되는지 count를 구하는 문제이다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2606 {
	static ArrayList<Integer> arr[];
	static boolean visited[];
	static int cnt, v;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n + 1];
		visited = new boolean[n + 1];
		
		for(int i = 1; i <=n; i++) {     // 인덱스 편의상 n+1설정, 0번째 요소는 사용 X  
			arr[i] = new ArrayList<>();
		}
		v = 1; // 탐색 시장할 정점의 번호
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[e].add(v);
			arr[v].add(e);
		}
		System.out.println(DFS(v));
	}
	private static int DFS(int i) {
		visited[i] = true;
		for(int b : arr[i]) {
			if(visited[b] == false) {
				cnt++;
				DFS(b);
			}
		}
		return cnt;
	}
}

오늘의 회고

오늘은 늦잠을 자고 게으름이 발동해서 점심 먹고 스터디 카페에 도착해서 DFS 한문제 밖에 풀지 못했습니다. 정신 차리고 내일 DFS문제를 더 풀겠습니다.