백준 2606번 -바이러스 (DFS)

 

 

DFS를 집중적으로 공부하기 위해서 기초문제부터 풀려고 하고 있습니다.

문제를 읽어보니 그래프를 먼저 생성하는 것이 필요하다고 생각해서 인접행렬과 인접리스트로 구현하는 방법 중

인접행렬로 그래프를 만들었습니다.

그래프를 구현할 때 중요한 것이 map의 크기인데요 배열의 index는 0부터 생성되나 그래프의 index는 1부터 사용하는 것이 더 편리하므로 +1을 해주는 것이 포인트입니다.

또한 dfs의 개념상 방문한 장소를 구별해야하므로 visited라는 배열을 생성해 체크해주었습니다.

인접행렬로 그래프를 생성후에는 1번과 연결된 컴퓨터의 숫자만 count하면 되기 때문에

dfs를 활용했습니다.

dfs의 재귀개념을 제대로 이해하지 못했는데 끝까지 찾다가 다 찾은 경우 다시 원래의 자리로 돌아간다라는 생각을 하니 이해가 더 쉬웠던 것 같습니다.

package com.company;

import java.util.Scanner;

public class Main {

    static int N, M;
    static int map[][];
    static boolean visited[];
    static int count = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num, num2;
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N+1][N+1];
        visited = new boolean[N+1];

        // Graph 인접행렬 만들기

        for(int i=0; i<M; i++){
            num = sc.nextInt();
            num2 = sc.nextInt();
            map[num][num2] = map[num2][num] = 1;
        }

        dfs(1);
        System.out.println(count);

    }

    public static void dfs(int start){
        visited[start] = true;

        for(int i=1; i<N+1; i++){
            if(visited[i]==false && map[start][i] == 1){
                count++;
                dfs(i);
            }
        }
    }
}