[백준]2606번 바이러스 - Java

문제

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

2606번: 바이러스

 

 

풀이

뭐 여러가지 방법을 풀 수 있겠지만 인접 행렬로 풀면 쓸데없는 메모리 활용이 좀 있을 것 같다.

그래서 ArrayList를 활용한 인접 리스트로 풀었음.

 

방문 체크 배열을 이용해서 이미 방문한 곳은 체크를 하고 인접한 애들 중 방문하지 않은 애들인 경우에만 answer++하고 dfs를 한번 더 탔음!

 

밑에 코드 참고!

 

 

코드

// 2606번 바이러스
// https://www.acmicpc.net/problem/2606

package BAEKJOON;

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

public class Num2606_바이러스 {
    static int N, M;
    static ArrayList<Integer>[] arrayLists;
    static boolean[] visited;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        arrayLists = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            arrayLists[i] = new ArrayList<>();
        }

        visited = new boolean[N + 1];

        for (int i = 0; i < M; i++) { // 해당 노드에 연결된 애들만 넣어줌
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            arrayLists[num1].add(num2);
            arrayLists[num2].add(num1);
        }

        solution(1);
        System.out.println(answer);
    }

    private static void solution(int number) {
        visited[number] = true;

        for (int i = 0; i < arrayLists[number].size(); i++) {
            int temp = arrayLists[number].get(i);
            if (!visited[temp]) { // 연결되어 있는 애들 중에 방문하지 않은 애들이 있으면 답++
                answer++;
                solution(temp);
            }
        }
    }
}