[ 알고리즘 ] 그래프
그래프
이미 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++;
}
}
}
}
}