[BOJ - JAVA] 2606 - 바이러스(DFS)

# 주소

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

2606번: 바이러스

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	static int[][] arr;
	static boolean[] visit;
	static int n;
	static int m;
    static int count;
    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		arr = new int[101][101];
		visit = new boolean[101];
		count = 1;
		for(int i = 0; i < m; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			arr[x][y] = arr[y][x] = 1;
		}
		dfs(1);
        System.out.println(count - 1);
    }
    public static void dfs(int i) {
    	visit[i] = true;
    	for(int j = 1; j <= n; j++) {
    		if(arr[i][j] == 1 && visit[j] == false) {
                count += 1;
    			dfs(j);
    		}
    	}
    }
}

이번에도 DFS문제를 가져왔습니다. 

문제를 잘 읽어보시면 노드의 시작은 1부터 출발합니다.

그러므로 방문하지 않은 값에 대해서는 과감하게 재껴두시고 1과 연결된 노드를 우선적으로 살핍니다.

지금 예제가 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

가 입력이 된다면 

노드의 연결을 2차원 행렬로 표현했을 때 이런 구조가 됩니다. 여기서 O가 1이고 /표시는 0입니다. 쉽게 말해 벽이라고 생각하면 되겠습니다.

그럼, 1을 기준으로 연결된 곳은 (2,1)과 (1,2)이므로 2와 연결되고, 다시 DFS에 2가 들어가 DFS(2)가 실행되면 (2,1)은 방문한 곳이므로 (2,3)이 실행됩니다. 그리고 DFS(3)이 실행되고 3으로 시작하는걸 찾으려니 어... 없죠?? 그럼 아까전의 DFS(2)일 때로 돌아갑니다.

이게 무슨 말이냐면, 우리는 DFS(2)를 실행했을 때 3이 나왔습니다. 그런데 DFS(3)은 실행했을 때 더 이상 값이 없었으므로 재귀 이전으로 돌아가 DFS(2)일 때 j값이 3이 아닌, 그 이후의 값을 찾을 거란 얘기입니다. 

그러므로 DFS(2)에서 j가 5일 때 visit[5] = false이고 arr값도 1이므로 다음으로 출력될 값은 5입니다. 이후, 5와 연결된 6을 이상으로 이전의 재귀로 계속 돌아간다 하더라도 출력될 값이 없는 것입니다.

이것을 노드로 표현한다면 

이런 느낌으로 접근할 수 있는 것입니다. 그러므로 문제에서의 출력값은 1을 포함한 값이므로 count에서 1을 빼주어 4를 출력하는 것이 원하는 답이될 것이고 만약 방문하는 노드를 모두 작성해야 한다면 1-2-3-5-6이 될 것입니다.

감사합니다!