그래프
1. 개념
-
노드(데이터)와 간선(관계)을 이용한 비선형 데이터 구조로, 데이터 간의 관계 표현에 사용
-
방향성: 간선은 방향(단방향/양방향)을 가졌는지 여부에 따라 방향 그래프, 무방향 그래프로 나뉨
-
가중치: 간선에는 가중치가 존재할 수 있음(ex. 1 -> 2 까지의 거리는 30)
-
순환여부: 특정 노드에서 간선을 따라 다시 돌아오는 순환이 존재하는 그래프가 존재할 수 있음
2. 구현
2-1. 인접행렬 - 2차원배열의 인덱스는 노드(행: 출발 노드, 열: 도착 노드), 값은 가중치
- 예시
package graph;
import java.util.Random;
public class AdjacenctMatrix {
static int[][] graph; // 인접행렬
static int n = 5; // 정점 수( 0 ~ N-1)
static Random random = new Random();
public static void main(String[] args) {
graph = new int[n][n];
printGraph();
}
// 가중치 설정
public static void weight(int from, int to) {
graph[from][to] = random.nextInt(10)+1; // 방향 그래프 가정
if(from == to) graph[from][to] = 0;
}
// 간선 추가 및 출력
public static void printGraph(){
System.out.println("인접행렬:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
weight(i,j);
System.out.print(graph[i][j] + " ");
}
System.out.println();
}
}
}-
출력 결과: ex. graph[0][1] = 2 -> 노드 0에서 1갈때의 cost = 2
-
장점
간선(A-B) 자체를 확인하는 시간복잡도가 O(1)로 좋으며, 구현 난이도가 낮음
List[A][B] -
단점
최악의 경우 N * N 크기의 행렬이 필요해 메모리 낭비 발생가능
노드 값 차이가 클 경우(ex. 1,2,99999) 제일 큰 수를 기준으로 크기 잡아야 함
2-2. 인접리스트 - 배열 인덱스는 시작노드, 값은 인접노드를 담은 리스트
- 예시
package graph;
import java.util.*;
public class AdjacencyList{
static int n = 5; // 정점 수
static List<Integer>[] graph;
public static void main(String[] args) {
// 인접리스트 초기화
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
// 간선 추가 (무방향)
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
// 출력
printGraph();
}
// 무방향 간선 추가
static void addEdge(int from, int to) {
graph[from].add(to);
graph[to].add(from); // 방향 그래프면 생략
}
// 그래프 출력
static void printGraph() {
System.out.println("가중치 없는 인접리스트:");
for (int i = 0; i < n; i++) {
System.out.print(i + " -> ");
for (int neighbor : graph[i]) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
}- 출력결과
가중치 없는 인접리스트:
0 -> 1 2
1 -> 0 2 3
2 -> 0 1 4
3 -> 1
4 -> 2 -
장점
원하는 노드(A)에 연결된 간선의 정보를 빠르게 파악 가능(인접행렬은 O(N)임)
공간복잡도 측면에서 인접행렬보다 낮은 비용(인접행렬은 10만 개 이상의 정점 가정 시 메모리 초과) -
단점
인접 행렬과 비교하여, 정점기준 연결된 간선을 모두 확인해야 해 번거로움
List[A] = [B,cost],[C,cost],...
3. 탐색
-
깊이우선탐색(DFS)
더 이상 탐색할 노드가 없을때 까지 간 후 최근 방문한 노드로 되돌아와 방문하지 않은 인접노드 방문 -
너비우선탐색(BFS)
현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어감 -
차이 예시
0
/ \
1 2
/ / \
3 4 5
(DFS) 0 → 1 → 3 → 2 → 4 → 5
(BFS) 0 → 1 → 2 → 3 → 4 → 53-1. 깊이 우선 탐색(DFS)
- 스택(stack) 예시
"가장 깊은 노드까지 탐색한 후 되돌아와(백트래킹) 인접노드의 방문여부를 확인하기"
1) 시작 노드를 설정 한 후 스택에 시작 노드 stack.push()
2) 스택이 비었는지 확인 stack.isEmpty() 후 비었다면 탐색 종료(모든 노드를 방문했음을 의미)
3) !stack.isEmpty()인 경우, stack.pop() ( = 최근에 push한 노드)
4) pop한 노드의 방문여부 확인 isVisited후
방문했다면 continue, 방문하지 않았다면 방문 처리 isVisited = true
5) 방문노드의 인접노드의 isVisited 여부 확인 해 방문하지 않은 노드를 스택에 push
->이 때, 인접노드를 오름차순으로 방문하고 싶다면 스택에 역순으로 push
요약
인접노드들은 일단 stack에 푸시해 둔 후, 스택에서 팝하는 순간에 방문 여부를 확인해 false인 경우 방문처리(중복 push 가능)
push: 방문예정(아직 방문처리 안함)
pop: 방문처리
package graph;
import java.util.*;
public class Dfs {
// 테스트케이스
private static int[][] graph = {
{1, 3}, {3, 4}, {4, 2}, {2, 5}};
static int start = 1; // 시작점
static int n = 5; // 탐색할 노드 수
// 필드 선언
private static List<Integer>[] adjList; // 인접리스트 저장할 배열
private static boolean[] visited; // 방문여부 저장
private static List<Integer> answer;
public static void main(String[] args) {
adjList = new ArrayList[n+1]; // 인덱스 = 시작노드, 값 = 도착노드(리스트 - 값이 여러개일 수 있음)
for(int i = 0; i < adjList.length; i++){
adjList[i] = new ArrayList<>();
}
for(int[] edge : graph){
adjList[edge[0]].add(edge[1]);
}
visited = new boolean[n+1];
answer = new ArrayList<>();
dfsIterative(start);
System.out.println(Arrays.toString(answer.stream().mapToInt(Integer::intValue).toArray()));
}
// 스택을 이용한 DFS 반복문 방식
private static void dfsIterative(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int now = stack.pop();
if (visited[now]) continue;
visited[now] = true; // 현재 노드를 방문했음
answer.add(now);
// 인접 노드를 역순으로 넣어야 낮은 숫자가 먼저 방문됨
List<Integer> neighbors = adjList[now];
Collections.reverse(neighbors);
for (int next : neighbors) {
if (!visited[next]) {
stack.push(next);
}
}
Collections.reverse(neighbors); // 원상 복구 (리스트는 참조형이라 구조 바뀌므로)
}
}
}- 재귀함수 순회 예시
package graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 깊이우선탐색
public class Dfs {
// 테스트케이스
private static int[][] graph = {
{1, 3}, {3, 4}, {4, 2}, {2, 5}};
static int start = 1; // 시작점
static int n = 5; // 탐색할 노드 수
// 필드 선언
private static List<Integer>[] adjList; // 인접리스트 저장할 배열
private static boolean[] visited; // 방문여부 저장
private static List<Integer> answer;
public static void main(String[] args) {
adjList = new ArrayList[n+1]; // 인덱스 = 시작노드, 값 = 도착노드(리스트 - 값이 여러개일 수 있음)
for(int i = 0; i < adjList.length; i++){
adjList[i] = new ArrayList<>();
}
/*
2차원배열인 graph에서 graph[0] ~ graph[4]의 값만 떼와서 가져옴
graph[0] = edge = [1,3], edge[0] = 1, edge[1] = 3
graph[1] = edge = [3,4], edge[0] = 3, edge[1] = 4 ...
adjList[시작노드] = [인접 노드 List] ex.) adjList[1] = [3], 1 -> 3
*/
for(int[] edge : graph){
adjList[edge[0]].add(edge[1]);
}
visited = new boolean[n+1];
answer = new ArrayList<>();
dfs(start);
System.out.println(Arrays.toString(answer.stream().mapToInt(Integer::intValue).toArray()));
}
//재귀함수를 이용해 스택처럼 구현
private static void dfs(int now){
visited[now] = true; //현재 노드 방문처리
answer.add(now);
for(int next : adjList[now]){
if(!visited[next]){
dfs(next); // 재귀호출
}
}
}
}
// 출력: 1 3 4 2 53-2. 너비 우선 탐색(BFS)
- 큐(queue)
요약
노드는 queue에 add 하기 전 방문여부를 확인해 false인 경우 add하며 방문처리(중복저장 불가),
poll하며 인접노드들을 순회해 방문여부 확인 후 방문처리
add: 방문예정(이지만 방문처리함)
poll: 인접노드 탐색 시작
package graph;
import java.util.*;
// 너비우선탐색
public class Bfs {
// 테스트케이스
private static int[][] graph = {
{1, 4}, {1, 2}, {2, 5}, {2, 6}, {4, 3}, {4, 7}, {5, 8}, {6, 8}, {3, 9}, {7, 9}};
static int start = 1; // 시작점
static int n = 9; // 탐색할 노드 수
private static List<Integer>[] adjList;
private static boolean[] visited;
private static List<Integer> answer;
public static void main(String[] args) {
adjList = new ArrayList[n+1];
for(int i = 0; i < adjList.length; i++){
adjList[i] = new ArrayList<>();
}
for(int[] edge : graph){
adjList[edge[0]].add(edge[1]); //adjList[1] = [2,4], adjList[2] = [5,6] ...
}
visited = new boolean[n+1];
answer = new ArrayList<>(n+1);
bfs(start);
System.out.println(Arrays.toString(answer.stream().mapToInt(Integer::intValue).toArray()));
}
private static void bfs(int start){
Deque<Integer> queue = new ArrayDeque<>();
queue.add(start);
visited[start] = true;
while(!queue.isEmpty()){
int now = queue.poll(); // 큐에 있는 것 빼내기(방문했으니) + 정답리스트에 추가 + 인접노드 탐색하기(for문)
answer.add(now);
for(int next : adjList[now]){
if(!visited[next]){
queue.add(next);
visited[next] = true;
}
}
/*
adjList[1] = [2,4] 이므로 2,4 순회, 각각 방문여부 확인 후 add
queue -> 4 / 2 / 1 에서 1, 2, 4 순으로 poll되며 각각의 인접노드 탐색 시작(큐 빌 때까지)
*/
}
}
}
// 출력 [1, 4, 2, 3, 7, 5, 6, 9, 8]
(구조)
1
↙ ↘
4 2
↙ ↘ ↙ ↘
3 7 5 6
↓ ↓ ↓ ↓
9 9 8 8
4. 심화개념 - 다익스트라(최단경로 구하기)
그래프 내 시작노드를 시준으로 각 노드까지의 최단 경로를 찾는 알고리즘으로,
음의 가중치가 존재할 경우 정상적으로 동작하지 않을 수 있음(즉 모든 가중치는 양수임을 가정)
- 흐름
-
시작 노드를 설정하고, 각 노드까지의 최소 가중치를 저장할 dist 배열을 INF로 초기화한다.
-
우선순위 큐(PriorityQueue)를 생성하여 시작 노드를 (비용 0)으로 큐에 추가한다.
-
큐에서 노드를 꺼낸다 (비용이 가장 작은 노드가 우선됨).
3-1. 이미 더 짧은 경로로 방문한 노드면 continue로 스킵한다.
3-2. 현재 노드의 인접 노드들을 순회하며, 새로 경유한 경로의 비용이 기존 비용보다 작다면
→ dist를 갱신하고, 우선순위 큐에 삽입한다.
-
큐가 빌 때까지 3번을 반복한다.
- 예시
package graph;
import java.util.*;
// 다익스트라(가중치)
public class Dijkstra {
private static int[][] graph = {
{0, 1, 2}, {0, 2, 5}, {1, 2, 1}, {1, 3, 2}, {2, 3, 3}}; // 출발노드 - 도착노드 - 가중치
private static int start = 0;
private static int n = 4;
//노드 번호와 가중치 저장
private static class Node{
int dest; // 도착 노드 번호
int cost; // 누적 가중치
public Node(int dest, int cost){
this.dest = dest;
this.cost = cost;
}
}
public static void main(String[] args) {
List<Node>[] adjList = new ArrayList[n];
for(int i = 0; i < n; i++){
adjList[i] = new ArrayList<>();
}
for(int[] edge : graph){
adjList[edge[0]].add(new Node(edge[1], edge[2]));
}
int[] dist = new int[n]; // 시작 노드에서 i번 노드까지 가는 최단 거리(비교용)
Arrays.fill(dist, Integer.MAX_VALUE); // 기본 가중치 무한대로 초기화
dist[start] = 0; // 시작 노드의 가중치는 0으로 초기화
// 우선순위 큐(최단거리일수록 우선순위가 높아 앞으로 옴)
Queue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node now = pq.poll();
// 지금 꺼낸 경로가 이미 저장된 최단거리보다 크면 무시
if (dist[now.dest] < now.cost) continue;
for (Node next : adjList[now.dest]) {
// 지금 꺼낸 경로+인접 노드로의 거리가 이미 저장된 최단거리보다 작다면 갱신 후 큐에 add
if (dist[next.dest] > now.cost + next.cost) {
dist[next.dest] = now.cost + next.cost;
pq.add(new Node(next.dest, dist[next.dest]));
}
}
}
System.out.println(Arrays.toString(dist));
}
}
// 결과 출력 [0, 2, 3, 4] <- 시작노드[0]에서 특정 노드[n+1]까지의 최소비용5. 추가 심화개념
5-1. 벨만-포드 알고리즘
다익스트라 알고리즘과 마찬가지로 시작 노드 - 특정 노드까지의 최소 비용을 구한다는 점에서는 같지만,
매 단계마다 모든 간선의 가중치를 다시 확인해 최소 비용을 갱신한다는 점에서 ' - 가중치'를 가진 그래프에서의 최단경로 계산도 가능하다는 점이 시사점이다.
- 흐름
-
시작 노드를 설정하고, dist 배열을 INF로 초기화한다. 시작 노드의 거리는 0으로 설정한다.
-
모든 간선을 N-1번 반복하면서 순회한다.
- 각 간선(u → v, cost)을 확인하며,
만약 dist[u] + cost < dist[v]인 경우 → dist[v]를 갱신한다.
- 각 간선(u → v, cost)을 확인하며,
-
N-1번 반복이 끝난 후, 모든 간선을 한 번 더 검사한다.
- 이때도 갱신이 발생하면 → 음수 사이클이 존재함을 의미한다.
-
dist 배열에는 시작점으로부터 각 정점까지의 최단 거리가 저장되어 있다.
5-2. 플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 모든 정점쌍 간의 최단 거리를 구하는 알고리즘으로,각 정점을 중간 거쳐가는 노드로 생각하며 거리 배열을 반복적으로 갱신한다.
음수 간선도 처리 가능하지만, 음수 사이클은 허용되지 않는다.
- 흐름
-
2차원 배열 dist[][]를 INF로 초기화하고, 자기 자신으로 가는 비용은 0으로 설정한다.
-
주어진 간선 정보를 바탕으로 dist[u][v] = cost로 초기화한다.
-
중간 정점 k를 0부터 N-1까지 순회하면서,
모든 정점 i와 j에 대해 다음 조건을 검사한다:- dist[i][j] > dist[i][k] + dist[k][j]이면 → dist[i][j]를 갱신한다.
-
모든 정점쌍 (i, j)에 대해 최단 거리가 dist[i][j]에 저장된다.
백트래킹
1. 개념
DFS와 BFS는 데이터를 전부 확인하는 완전 탐색으로, 모든 경우의 수를 탐색하므로 비효율적임
유효한 해의 집함을 그래프로 표현하고 유망함수를 정의해 "가능성이 있는 곳만 탐색하고, 없을 경우 되돌아가는" 백트래킹 알고리즘으로 해를 찾는 방법
+)깊이우선탐색도 더 이상 탐색할 경로가 없을 때 백트래킹을 활용했지만, 백트래킹은 정답이 될 가능성이 존재하지 않다고 판단했을 때 백트래킹을 활용함
2. 예제
-
체스 퀸 예시
-
1 ~ N 까지의 합이 sum을 만족하는 조합
package backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BackTracking {
private static List<List<Integer>> result;
private static int n = 5;
public static void main(String[] args) {
result = new ArrayList<>();
backtracking(0, new ArrayList<>(), 1);
System.out.println(Arrays.toString(result.toArray()));
}
private static void backtracking(int sum, List<Integer> selectedNums, int start){
if(sum == 7){ // 합이 7이 되는 조합을 찾는다
result.add(selectedNums);
return;
}
for(int i = start; i <= n; i++){
if(sum + i <= 7) { // 누적합이 7 이하일 때만 시도
List<Integer> list = new ArrayList<>(selectedNums);
list.add(i);
backtracking(sum + i, list, i + 1); // 재귀호출
}
}
/*
재귀 흐름
1-1) if문 조건을 만족하면, 새로운 재귀함수 호출
1-2) if문 조건을 만족하지 못하면 , 재귀함수내의 for문 루프를 계속 돌다가 종료
2) for문 루프 돌며 다시 호출된 재ㅐ귀함수가 sum == 7의 if문 조건 만족시 return 만나 종료
3) 모든 재귀함수가 종료되면, 초반의 for문으로 돌아와 i가 1씩 증가하며 for문 순회
*/
}
}
// 결과 출력 [[2, 5], [3, 4]]