[ 알고리즘 ] 그래프

大코딩시대

 

그래프

이미 DFS와 BFS에 대해서 글을 작성했지만, 그 전에 그래프에 대해 먼저 알고 가야한다.

 

그래프의 정의는

실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용하는것이고,

간선은 방향이 없거나, 방향이 있을 수 있다.

 

코딩테스트에 자주 나오는 자료구조이므로 꼭 이해하고 있어야한다.

탐색( DFS, BFS ), 트리에서도 사용한다.

 

그래프를 구현하는 3가지 방법은

• 엣지 리스트 (순서에 맞게 배열에 저장하는 방식으로 사용 불편)
• 인접 행렬 (2차원 배열 구조로 공간 복잡도 제약)
• 인접 리스트 (ArrayList로 구현, 가장 많이 사용)

인접리스트를 나도 가장 많이 사용했고, HashMap이나 ArrayList로 구현을 하면된다.

 

종류

1. 가중치가 없는 그래프

ArrayList<Integer>[N]

[1] : [2,3]

[2] : [3,4]

 

 

2. 가중치가 있는 그래프

ArrayList<Node>[N]

[1] : [(2,5), (3,6)]

[2] : [(3,7), (4,8)]

 

---

문제 - 백준 2606번 바이러스

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

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

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

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

4

 

---

문제풀이

연습해보려고 DFS,BFS 둘 다로 풀어봤다.

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

public class Main {
    static int[][] arr;
    static boolean[] visited;
    static int N, T, result;
    static Queue<Integer> queue;

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

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

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x][y] = 1;
            arr[y][x] = 1;
        }

        //bfs로 풀기
        queue = new LinkedList<>();
//        result = 0;
//        bfs(1);
//        System.out.println(result);

        //dfs로 풀기
        result = 0;
        dfs(1);
        System.out.println(result - 1);
    }

    static void dfs(int V) {
        visited[V] = true;
        result++;
        for (int i = 0; i < N + 1; i++) {
            if (arr[V][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

    static void bfs(int n) {
        visited[n] = true;
        queue.add(n);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int i = 1; i < N + 1; i++) {
                if (arr[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                    result++;
                }
            }
        }
    }


}