그래프
그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다.
여기서는 그래프를 구현하는 3가지 방법을 알아본다.
에지 리스트 (edge list)
에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
에지 리스트로 가중치 없는 그래프 표현하기
가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. 노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer 형이다.
1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한다. 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 그리고 노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라 한다. (만약 방향이 없는 그래프라면 [1, 2], [2, 1]은 같은 표현일 것이다.)
에지 리스트로 가중치 있는 그래프 표현하기
가중치 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다. 다음 그림을 보자.
1에서 2로 향하는 가중치가 8인 에지는 [1, 2, 8]로 표현한다. 이처럼 에지 리스트는 구현하기가 쉽다. 하지만 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. 에지 리스트는 벨만 포드나 크루스칼(MST) 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.
인접 행렬 (adjacency matrix)
인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다. 다음은 노드가 5개인 그래프를 5 x 5 인접 행렬로 표현한 것이다.
인접 행렬로 가중치 없는 그래프 표현하기
다음 그림을 보면 1에서 2를 향하는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다. 1을 저장하는 이유는 가중치가 없기 때문이다. 1에서 2로 향하는 에지가 있다는 표시를 노드 중심으로 한다고 이해하면 된다.
인접 행렬로 가중치 있는 그래프 표현하기
앞의 가중치가 없는 그래프를 이해했다면 가중치가 있는 그래프는 그림만 쓱 봐도 쉽게 이해할 수 있을 것이다. 2에서 5로 향하는 에지의 가중치를 2행 5열에 기록한다.
이처럼 인접 행렬을 이용한 그래프 구현은 쉽다. 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 것도 장점이다. 하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. 또한 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다. 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력도 필요하다. 예를 들어 노드가 3만 개가 넘으면 자바 힙 스페이스(java heap space) 에러가 발생한다.
인접 리스트 (adjacency list)
인접 리스트는 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언한다. 자료형은 경우에 맞게 사용한다.
인접 리스트로 가중치 없는 그래프 표현하기
다음은 인접 리스트로 가중치 없는 그래프를 표현한 것이다. 현재의 경우 Integer형이면 그래프를 표현하기에 충분하므로 ArrayList<Integer>[5]로 선언했다. 인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
예를 들어 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2, 3]을 연결하는 방식으로 표현한다.
인접 리스트로 가중치 있는 그래프 표현하기
가중치가 있는 경우 자료형을 클래스로 사용한다. 다음은 (도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한 것이다.
그림을 보면 ArrayList[1]에 [(2, 8), (3, 3)]이 연결되어 있다. 이는 노드1과 2가 가중치 8 에지로, 노드1과 3이 가중치 3 에지로 연결되어 있다는 것을 보여준다. 방향성도 고려되어 있다. 그래프를 구현하는 다른 방법에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편이다. 하지만 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다. 이런 장점으로 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
[백준 18352번] 특정 거리의 도시 찾기
https://www.acmicpc.net/problem/18352
모든 도로의 거리가 1이므로 가중치가 없는 인접 리스트로 이 그래프를 표현할 수 있다. 도시의 개수가 300,000, 도로의 최대 크기가 1,000,000 이므로 BFS 탐색을 수행하면 문제를 시간 복잡도 안에서 해결할 수 있다.
1. 인접 리스트로 도시와 도로 데이터의 그래프를 구현한다.
2. BFS 탐색 알고리즘으로 탐색을 수행하면서 각 도시로 가는 최단 거릿값을 방문 배열에 저장한다.
최초에는 방문 도시가 1이고, 이동하지 않았으므로 방문 배열에 0을 저장한다. 이후 방문하는 도시는 이전 도시의 방문 배열값 + 1을 방문 배열에 저장하는 방식으로 이동 거리를 저장한다. 예를 들어 방문 배열[2]에는 이전 도시의 방문 배열값이 0이므로 0 + 1을 기록한다.
3. 탐색 종료 후 방문 배열에 값이 K와 같은 도시의 번호를 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int visited[];
static ArrayList<Integer>[] A;
static int N,M,K,X;
static List<Integer> answer;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
N = scan.nextInt(); // 정점의 수
M = scan.nextInt(); // 간선의 수
K = scan.nextInt(); // 간선의 수
X = scan.nextInt(); // 간선의 수
A = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++) {
int S = scan.nextInt();
int E = scan.nextInt();
A[S].add(E);
}
visited = new int[N + 1]; //방문 배열 초기화
for(int i = 0; i <= N; i++){
visited[i] = -1;
}
BFS(X);
boolean isAnswer = false;
for(int i = 0; i <= N; i++){
if(visited[i] == K) {
System.out.println(i);
isAnswer = true;
}
}
if(!isAnswer){
System.out.println("-1");
}
}
// BFS구현
private static void BFS(int node) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(node);
visited[node]++;
while (!queue.isEmpty()) {
int now_node = queue.poll();
for (int i : A[now_node]) {
if (visited[i] == -1) {
visited[i] = visited[now_node] + 1;
queue.add(i);
}
}
}
}
}
여기서는 visited 배열을 int형으로 전부 -1로 초기화 해 -1이면 방문하지 않은 노드, 아니라면 거리를 대입함으로써 visited와 distance 역할을 둘 다 하고 있다.
[백준 1325번] 효율적인 해킹
https://www.acmicpc.net/problem/1325
N과 M의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않은 편이다. 이 문제에서 잘 확인해야 할 부분은 신뢰 관계가 A, B라고 했을 때, A가 B를 신뢰한다는 것이다. 또한 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다. 그래프의 노드와 에지를 기준으로 이해하면 A라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B, C라고 하면 B, C는 A에게 신뢰받는 노드가 된다.
1. 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프를 표현한다.
2. 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 준다.
3. 탐색 종료 후 신뢰도 배열을 탐색해 신뢰도의 최댓값을 Max값으로 지정하고, 신뢰도 배열을 다시 탐색하면서 Max값을 지니고 있는 노드를 오름차순 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] answer;
static ArrayList<Integer>[] A;
static int N, M;
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new ArrayList[N+1];
answer = new int[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
A[a].add(b);
}
for (int i = 1; i <= N; i++) {
visited = new boolean[N + 1];
BFS(i);
}
int max = 0;
for (int i = 1; i <= N; i++) {
max = Math.max(max, answer[i]);
}
for (int i = 1; i <= N; i++) {
if(answer[i] == max) System.out.print(i + " ");
}
}
private static void BFS(int n) {
Queue<Integer> queue = new LinkedList<>();
queue.add(n);
visited[n] = true;
while (!queue.isEmpty()) {
int now = queue.poll();
for (int i : A[now]) {
if(!visited[i]) {
answer[i]++;
visited[i] = true;
queue.add(i);
}
}
}
}
}
난 DFS로 했는데 BFS로 해도 상관없다. ArrayList A에 (a, b) 순서로 넣어야 간선을 타고 가면서 가장 많이 쌓이는 곳을 해킹하는 식으로 접근이 가능한데 신뢰 관계가 헷갈려서 (b, a) 순서로 넣었다. 그리고 answer 배열을 2차원 배열로 만들어서 시작 부분이 다를 때마다 2차원 인덱스를 하나 늘렸는데 문제가 최댓값의 인덱스를 찾는거지 최댓값을 찾는게 아니니 그냥 1차원 배열로 누적으로 더한 후 최댓값의 인덱스를 출력하면 됐다.
[백준 1707번] 이분 그래프
https://www.acmicpc.net/problem/1707
노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할할 수 있다고 한다. 잘 생각해 보면 트리의 경우에는 항상 이분 그래프가 된다는 것을 알 수 있다. 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다. 단, 사이클이 발생했을 때는 이런 이분 그래프가 불가능할 때가 있다. 바로 다음과 같을 때이다.
이때는 3번 노드를 1번 집합으로 설정하면 1번 노드와 인접하면서 같은 집합에 속하게 되고, 2번 집합으로 설정하면 2번 노드와 인접하면서 같은 집합에 속하게 돼 이분 그래프가 불가능하다. 그렇다면 이때를 어떻게 도출할 수 있을까? 바로 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는 것으로 판별할 수 있다.
1. 입력된 그래프 데이터를 인접 리스트로 구현한다.
2. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다. 실행 결과가 이분 그래프가 아니면 이후 노드는 탐색하지 않는다.
3. 이분 그래프 여부를 정답으로 출력한다.
출발 노드(4)와 도착 노드(2)의 집합이 같으므로 이분 그래프 불가능 => NO 출력
4. 사례의 개수만큼 과정 1 ~ 3을 반복한다.
- 여기에서 모든 노드로 DFS를 실행하는 이유는 그래프의 모든 노드가 이어져 있지 않고, 여러 개의 부분 그래프로 이뤄진 케이스가 존재할 수 있기 때문이다.
+ 근데 BFS로 풀어도 상관없다 모든 정점 돌면서 아직 안 돈 곳 있으면 찾아서 거기부터 다시 돌면 되니까.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] A;
static int[] check;
static boolean visited[];
static boolean IsEven;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int t = 0; t < N; t++) {
String[] s = br.readLine().split(" ");
int V = Integer.parseInt(s[0]);
int E = Integer.parseInt(s[1]);
A = new ArrayList[V + 1];
visited = new boolean[V + 1];
check = new int[V + 1];
IsEven = true;
for (int i = 1; i <= V; i++) {
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < E; i++) { // 인접 리스트로 그래프 저장
s = br.readLine().split(" ");
int Start = Integer.parseInt(s[0]);
int End = Integer.parseInt(s[1]);
A[Start].add(End);
A[End].add(Start);
}
for (int i = 1; i <= V; i++) { // 주어진 그래프가 하나로 연결되어 있다는 보장이 없으므로 모든 정점에서 수행
if (IsEven)
DFS(i);
else
break;
}
if (IsEven)
System.out.println("YES");
else
System.out.println("NO");
}
}
public static void DFS(int node) { // DFS구현
visited[node] = true;
for (int i : A[node]){
if (!visited[i]) {
check[i] = (check[node] + 1) % 2; // 인접한 정점은 같은 집합이 아니므로 이전 정점과 다른 집합으로 처리
DFS(i);
}
else if (check[node] == check[i]){ // 이미 방문한 정점이 현재 내 정점과 같은 집합이면 이분 그래프가 아님
IsEven = false;
}
}
}
}
[BFS]
import java.io.*;
import java.util.*;
public class Main {
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 = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken()); // 정점 개수
int E = Integer.parseInt(st.nextToken()); // 간선 개수
ArrayList<Integer>[] A = new ArrayList[V+1];
int[] data = new int[V+1];
for (int j = 1; j <= V; j++) {
A[j] = new ArrayList<>();
}
for (int j = 0; j < E; j++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
A[u].add(v);
A[v].add(u);
}
Queue<Integer> queue = new LinkedList<>();
int[] visited = new int[V+1];
String strAnswer = "YES";
for (int j = 1; j <= V; j++) {
if (visited[j] == 0) {
queue.add(j);
visited[j] = 1;
}
while (!queue.isEmpty()) {
int now = queue.poll();
for (int a : A[now]) {
if(visited[a] == 0) {
visited[a] = 3 - visited[now];
queue.add(a);
}
else if(visited[a] == visited[now]){
strAnswer = "NO";
break;
}
}
}
}
bw.append(strAnswer + "\n");
}
bw.flush();
bw.close();
}
}
이분 그래프의 정의를 정확히 알았다면 더 쉽게 풀 수 있을 것 같은 문제. 저렇게 각 점을 서로 다른 2개의 색깔로 색칠했을 때 한 변이 서로 다른 색깔로 칠해져 있다면 이분 그래프이다. 만약 한 변이 같은 빨간색이나, 같은 초록색으로 양 쪽 두 개가 칠해져 있다면 이분 그래프가 아닌 것.
[백준 2251번] 물통
https://www.acmicpc.net/problem/2251
지금까지 접해 봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다. A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고, 문제에 접근해 보자.
1. 처음에 물통 A, B는 비어 있고, C는 꽉 차 있으므로 최초 출발 노드를 (0, 0, 3번째 물통의 용량)으로 초기화한다.
2. BFS를 수행한다. 탐색 과정은 다음과 같다.
1. 노드에서 갈 수 있는 6개의 경우(A -> B, A -> C, B -> A, B -> C, C -> A, C -> B)에 관해 다음 노드로 정해 큐에 추가한다. A, B, C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않는다.
2. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남긴다.
3. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 배열에 추가한다.
3. 정답 리스트를 오름차순 출력한다.
10 1 2 8 9를 오름차순으로 정렬 후 출력 => 1, 2, 8, 9, 10
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] Sender = {0, 0, 1, 1, 2, 2};
static int[] Receiver = {1, 2, 0, 2, 0, 1};
static boolean visited[][]; // A, B의 무게만 있으면 C의 무게가 고정되므로 2개만 체크
static boolean answer[]; // A의 무게가 0일 때 C의 값 저장 표시 위해
static int now[]; // A, B, C 값 저장 배열
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
now = new int[3];
now[0] = sc.nextInt();
now[1] = sc.nextInt();
now[2] = sc.nextInt();
visited = new boolean[201][201];
answer = new boolean[201];
BFS();
for (int i = 0; i < answer.length; i++) {
if (answer[i]) System.out.print(i + " ");
}
}
public static void BFS() {
Queue<AB> queue = new LinkedList<>();
queue.add(new AB(0, 0)); // A와 B의 물의 양 0
visited[0][0] = true; // 일 때 방문 확인 true로
answer[now[2]] = true; // 하고 answer[10]도 true로. (예제1) (A가 비었을 때 C가 될 수 있는 경우 중 하나이므로)
while (!queue.isEmpty()) {
AB p = queue.poll();
int A = p.A;
int B = p.B;
int C = now[2] - A - B; // C는 전체 물의 양에서 A와 B를 뺀 것
for (int k = 0; k < 6; k++) { // A -> B, A -> C, B -> A, B -> C, C -> A, C -> B
int[] next = {A, B, C};
next[Receiver[k]] += next[Sender[k]]; // 받는 물통에 보내려는 물통의 값 더하기
next[Sender[k]] = 0; // 보내는 물통의 값 0으로 업데이트
if (next[Receiver[k]] > now[Receiver[k]]) { // 만약 물이 넘칠 때
// 초과하는 만큼 다시 이전 물통에 넣어 줌
next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
next[Receiver[k]] = now[Receiver[k]]; // 대상 물통은 최대로 채워 줌
}
if(!visited[next[0]][next[1]]) { // A와 B의 물의 양을 이용해 방문 배열 체크
visited[next[0]][next[1]] = true;
queue.add(new AB(next[0], next[1]));
if (next[0] == 0) { // A의 물의 양이 0일 때 C의 물의 무게를 정답 변수에 저장
answer[next[2]] = true;
}
}
}
}
}
// AB 클래스 선언 -> A와 B의 값만 지니고 있으면 C는 유추할 수 있으므로 두 변수만 사용하기
static class AB {
int A;
int B;
public AB(int A, int B) {
this.A = A;
this.B = B;
}
}
}
그래프가 주어지고 이를 바탕으로 탐색하는 것이 아니라 그래프의 원리를 이용해 역으로 그래프를 생각해 내는 문제이다. 처음 접한 거라 접근 방법조차 생각해 내지 못했다. 코드를 잘 기억해두자. 또한 물통의 양을 노드로 만들어 탐색했는데 이런 방식도 기억해 두자.
[참고 자료]
- Do it! 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 위상 정렬 (1) | 2024.06.11 |
|---|---|
| 유니온 파인드 (0) | 2024.06.07 |
| 정수론 - 확장 유클리드 호제법 (0) | 2024.06.01 |
| 정수론 - 유클리드 호제법 (0) | 2024.05.31 |
| 정수론 - 오일러 피 (0) | 2024.05.30 |
