[백준] 2606 바이러스

문제

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

2606번: 바이러스

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2606_바이러스 {
	static int N,M;
	static int[][] map;
	static boolean[] visited;
	public static void main(String[] args) throws Exception{
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(in.readLine());	//컴퓨터의 수
		M = Integer.parseInt(in.readLine());	//연결된 링크의 수
		
		map = new int[N][N];
		visited = new boolean[N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			map[a][b] = map[b][a] = 1;
		}
		
		dfs(0);
		
		int result = -1;
		for (int i = 0; i < N; i++) {
			if(visited[i]) {
				result++;
			}
		}
		System.out.println(result);
	}
	private static void dfs(int cur) {
		visited[cur] = true;
		
		for (int i = 0; i < N; i++) {
			if(map[cur][i] == 1 && !visited[i]) {
				dfs(i);
			}
		}
	}

}

소스코드 풀이

- DFS를 통해서 노드간 방문체크(visited)

- 방문체크 되어있는 노드를 카운트

Review

플로이드 와샬 유형인 줄 알고 푼 건데 플로이드 와샬 유형이 아니었...

그냥 워밍업 느낌으로 풀었다. 시작 정점이 고정되어 있어서 어렵지 않았던 문제

다른 친구는 DisJoint로 풀었는데 다음주에 개념을 쫙 정리해야 겠다... 다 까먹었다...