[알고리즘] 백준 2660 바이러스 -bfs, dfs-

 

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

2606번: 바이러스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int startNode = 1;
    static int nodeCnt = 0;
    static int edgeCnt = 0;
    static boolean isVisited[];
    static LinkedList<Integer> edgeList[];
    static int result = 0;

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

        nodeCnt = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        edgeCnt = Integer.parseInt(st.nextToken());

        //노드방문 boolean 생성
        isVisited = new boolean[nodeCnt + 1];

        //노드 연결리스트 생성
        edgeList = new LinkedList[nodeCnt + 1];
        for(int i=0; i<= nodeCnt; i++){
            edgeList[i] = new LinkedList();
        }

        // 간선 세팅
        for(int i=0; i < edgeCnt; i++ ){
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            edgeList[node1].add(node2);
            edgeList[node2].add(node1);
        }

        dfs(startNode, isVisited);
        //자신이 감염시킨 컴퓨터 수가 결과이므로 -1 해줌
        System.out.println(result-1);
    }

    public static void dfs(int currentNode, boolean[] visited){
        if(visited[currentNode]){
            return;
        }
        visited[currentNode] = true;
        for(int nextNode : edgeList[currentNode]){
            dfs(nextNode, visited);
        }
        result++;
    }

}

 

링크드리스트와 dfs를 사용해서 풀었다.

감염시킨 컴퓨터 수가 결과이므로 결과에서 자신을 제외하기 위해 -1을 해주어야한다.

 

 

 

다음은 인접행렬로 풀어본 풀이입니다.

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] map;
    static boolean[] bfsVisited;
    static int virusCnt = 0; //바이러스 걸리게되는 컴퓨터 수
    private static int N; //컴퓨터 수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N + 1][N + 1];
        bfsVisited = new boolean[N + 1];
        int comSize = sc.nextInt();
        for (int i = 1; i <= comSize; i++) {
            int node1 = sc.nextInt();
            int node2 = sc.nextInt();
            map[node1][node2] = 1;
            map[node2][node1] = 1;
        }
        bfs(1);
        System.out.println(virusCnt);
    }

    static void bfs(int currentNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(currentNode);
        bfsVisited[currentNode] = true;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            for (int i = 1; i <= N; i++) {
                if (map[currentNode][i] == 1 && !bfsVisited[i]) {
                    queue.offer(i);
                    bfsVisited[i] = true;
                    virusCnt++;
                }
            }
        }
    }

}

 

 

[Kotlin]

package kotlin

import java.util.*


lateinit var map: Array<IntArray>
lateinit var bfsVisited: BooleanArray
private var virusCnt = 0 //바이러스 걸리게되는 컴퓨터 수
private var N: Int = 0 //컴퓨터 수


fun main(vararg args: String) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    map = Array(N + 1) { IntArray(N + 1) }
    bfsVisited = BooleanArray(N + 1)
    val comSize = sc.nextInt()
    for (i in 1..comSize) {
        val node1 = sc.nextInt()
        val node2 = sc.nextInt()
        map[node1][node2] = 1
        map[node2][node1] = 1
    }
    bfs(1)
    println(virusCnt)
}

fun bfs(currentNode: Int) {
    var currentNode = currentNode
    val queue = LinkedList<Int>()
    queue.offer(currentNode)
    bfsVisited[currentNode] = true
    while (!queue.isEmpty()) {
        currentNode = queue.poll()
        for (i in 1..N) {
            if (map[currentNode][i] == 1 && !bfsVisited[i]) {
                queue.offer(i)
                bfsVisited[i] = true
                virusCnt++
            }
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!
github.com/mtjin/algorithm_practice

mtjin/algorithm_practice