자바랑 코덕코덕

[문제]

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

[문제 풀이]

이 문제는 BFS 또는 DFS를 이용하여 해결 할 수 있다.

그리고 BFS와 DFS를 구현하는데 matrix 또는 list로 구현이 가능한데 두 가지 방법으로 다 풀어보았다.

1. BFS Linked list

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

public class Main {
    static int N, M;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;
    static Node[] adj;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        visited = new boolean[N+1];
        adj = new Node[N+1];

        for (int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

        System.out.println(bfs(1));
    }

    public static int bfs(int n) {
        int cnt = 0;
        visited[n] = true;
        q.offer(n);

        while(!q.isEmpty()) {
            int x = q.poll();

            for (Node node=adj[x]; node!=null; node=node.next) {
                if (!visited[node.n]) {
                    q.offer(node.n);
                    visited[node.n] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

2. DFS Linked list

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

public class Main {
    static int n, m;
    static Node[] adj;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        adj = new Node[n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (Node node=adj[v]; node!=null; node=node.next) {
            if (!visit[node.n]) {
                cnt++;
                dfs(node.n);
            }
        }
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

3. DFS Matrix

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

public class Main {
    static int n, m;
    static int[][] matrix;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        matrix = new int[n+1][n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            matrix[u][v] = 1;
            matrix[v][u] = 1;
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (int i=1; i<=n; i++) {
            if (matrix[v][i]==1 && !visit[i]) {
                cnt++;
                dfs(i);
            }
        }
    }
}

[결과]

BFS - list

DFS - list

DFS - matrix

순으로 결과는 다음과 같이 나왔다.

[문제]

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

[문제 풀이]

제거할 노드를 부모로 가지고 있는 모든 노드들을 제거하기 위해 BFS를 사용했다.

delete(int node) 함수는 bfs를 구현한 것으로 (제거할 노드 == 부모 노드) 일때 큐에 넣어주고 하나씩 꺼내면서 제거해 주었다.

제거하면서 boolean 변수 visited=true로 방문체크를 하였다.

이후 leaf 노드를 찾기 위해 방문을 안한 노드를 찾아가면서 노드가 가리키는 숫자는 부모노드이므로 그 숫자들을 방문 체크하였다.

결국 하나도 방문하지 않은 노드가 leaf 노드가 된다.

방문하지 않는 노드 수를 세서 출력해주면 leaf 노드의 수가 나온다.

[코드]

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

public class Main {

    static int N;
    static int[] parents;
    static int removeNode;
    static boolean[] visited;
    static boolean[] leaves;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        parents = new int[N];
        visited = new boolean[N];
        leaves  = new boolean[N];
        Arrays.fill(leaves, true);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            parents[i] = stoi(st.nextToken());
        }

        removeNode = stoi(br.readLine());
        if (parents[removeNode] == -1) {
            System.out.println(0);
            return;
        }

        delete(removeNode);

        for (int i=0; i<N; i++) {
            if (parents[i] == -1) continue;
            if (!visited[i]) {
                leaves[parents[i]] = false;
            }
        }
        
        int ans = 0;
        for (int i=0; i<N; i++) {
            if (leaves[i]) ans++;
        }
        System.out.println(ans);
    }

    static void delete(int node) {
        visited[node] = true;
        leaves[node] = false;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i=0; i<N; i++) {
                if (cur == parents[i] && !visited[i]) {
                    visited[i] = true;
                    leaves[i] = false;
                    queue.offer(i);
                }
            }
        }
    }
}

[실행 결과]

실행 결과는 위와 같다.