[백준] 2606 바이러스(실버3) - 그래프(DFS)

문제

코드

시도1 - 인접 행렬O

이번 문제는 특정 노드에 연결된 노드들을 탐색하는 것이 핵심이다.
인접 행렬과 인접 리스트 모두 가능한데 우선 인접 행렬을 이용하여 구현해봤다.

1. 2차원 배열로 정점간의 연결 유무를 구현한다.
2. DFS를 이용하여 특정 정점(target)과 연결된 정점을 찾고 HashSet에 저장한다.
   • 연결된 정점이 HashSet에 존재하지 않다면 연결된 정점을 target으로 DFS를 실행한다.
     사실 DFS는 생각하지 못했고 재귀만 생각하고 풀었는데 풀고 살펴보니 DFS를 이용한 풀이였다.

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

public class _2606 {
    static int[][] graph;
    static HashSet<Integer> hs = new HashSet<>();
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vertexCnt = Integer.parseInt(br.readLine());
        int edgeCnt = Integer.parseInt(br.readLine());

        // 인접 행렬 그래프: 탐색이 핵심이기 때문에 인접 리스트가 아닌 인접 행렬을 이용해 구현
        graph = new int[vertexCnt+1][vertexCnt+1];
        for (int i = 0; i < edgeCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int vertex1 = Integer.parseInt(st.nextToken());
            int vertex2 = Integer.parseInt(st.nextToken());

            graph[vertex1][vertex2] = 1;
            graph[vertex2][vertex1] = 1;
        }

        hs.add(1);
        search(1);

        // 아래 코드처럼 1에 연결된 노드들을 먼저 해시에 넣고 시작하면 시간이 더 적게 걸림..
//        for (int i = 0; i < graph[1].length; i++) {
//            if (graph[1][i] == 1 && !hs.contains(i)) {
//                hs.add(i);
//                search(i);
//            }
//        }
        System.out.println(hs.size()-1);


    }

    public static void search(int target) {
        for (int i = 0; i < graph[target].length; i++) {
            if (graph[target][i] == 1 && !hs.contains(i)) {
                hs.add(i);
                search(i);
            }
        }
    }
}

 

 

시도2 - 인접 리스트O

인접 리스트를 이용하여 그래프를 구현한 코드이다. 코드 구성은 로직1과 같다. 다만 인접 행렬 방식은 모든 노드와 연결 여부를 확인해야 하는 반면 인접 리스트는 에초에 연결된 노드들만 리스트에 저장하기 때문에 다른 노드와 연결 여부를 확인하지 않는다.

import java.io.*;
import java.util.*;

public class _2606 {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    static int count = 0;

    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()); // 연결의 수

        // 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        visited = new boolean[n + 1];

        dfs(1); // 1번 컴퓨터부터 시작

        System.out.println(count - 1); // 1번 컴퓨터 제외
    }

    static void dfs(int v) {
        visited[v] = true;
        count++;

        for (int i : graph.get(v)) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }
}

 

1년 전 풀이 - O

아래 코드는 1년 전 내가 작성한 코드이다. 시도1과 코드 구성은 똑같지만 HashMap이 아닌 배열을 이용하여 풀었다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class _2606 {
    public static boolean [] visited;
    public static int[][] arrGraph;
    public static int num;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int pair = Integer.parseInt(br.readLine());

        // arrGraph 초기화
       arrGraph = new int[n+1][n+1];
        visited = new boolean[n+1];
        Arrays.fill(visited, false);

        for (int i = 0; i < pair; i++) {
            int n1, n2;
            st = new StringTokenizer(br.readLine(), " ");
            n1 = Integer.parseInt(st.nextToken());
            n2 = Integer.parseInt(st.nextToken());
            // n1*n2 = 1 삽입(연결된다는 뜻)
            arrGraph[n1][n2] = arrGraph[n2][n1]= 1;
        }
        dfs(1, n);
        // 1번 컴퓨터는 뺴야 하니깐 num-1
        System.out.println(num-1);
    }
    // 재귀를 이용한 dfs
    public static void dfs(int node, int n) {
        visited[node] = true; // 현재 노드(1) 방문 처리
        num += 1; // 감염된 컴퓨터 추가
        // node번쨰 행을 돌면서 연결된 노드가 있는지 확인
        // 연결된 노드가 있다면 그 노드로 가서(연결된 노드의 행으로 가서) 연결된 노드가 있는지 확인
        // 만약 연결된 노드가 없다면 함수가 종료되면서 바로 전 노드로 돌아옴
        int k = 0;
        for (int i = 1; i <= n; i++) {
            // 이후 노드에 방문하지 않았다면
            if (arrGraph[node][i] == 1 && visited[i] == false)
                dfs(i, n);
        }
    }
}