7주차
Graph는 정점(Vertex, Node) 과 간선(Edge) 으로 이루어진 비선형 자료 구조이며, 여러 대상 사이의 연결 관계를 표현할 때 사용됩니다.
배열이나 문자열처럼 데이터가 일렬로 이어지는 구조와 달리, 그래프는 하나의 정점에서 여러 정점으로 연결될 수 있고 다시 다른 정점과 이어질 수 있기 때문에 코딩 테스트에서는 도시 간 이동, 컴퓨터 네트워크, 친구 관계, 도로 연결, 작업 순서, 그룹 관계처럼 대상 사이의 관계가 주어지는 문제에서 자주 등장합니다.
비선형 자료 구조는 데이터가 일렬로 나열되지 않고, 하나의 데이터가 여러 데이터와 연결될 수 있는 구조를 의미합니다.
배열, 문자열, 스택, 큐처럼 앞뒤 관계가 비교적 단순한 구조는 선형 자료 구조에 가깝지만, 그래프는 정점과 간선의 연결 방식에 따라 여러 갈래로 나뉘거나 다시 돌아오는 구조를 만들 수 있습니다.
- Graph
- Tree
- Heap
- Hash Table
Vertex는 그래프를 구성하는 하나의 지점 또는 대상을 의미합니다.
예를 들어 도시 연결 문제에서는 각 도시가 정점이 되고, 컴퓨터 네트워크 문제에서는 각 컴퓨터가 정점이 됩니다.
- 도시
- 사람
- 컴퓨터
- 지하철역
- 웹 페이지
- 게임 맵의 한 칸
Edge는 정점과 정점을 연결하는 관계 또는 경로를 의미합니다.
예를 들어 두 도시 사이에 도로가 있다면 그 도로는 간선이 되고, 두 사람이 친구 관계라면 그 친구 관계도 간선으로 볼 수 있습니다.
- 도시 사이의 도로
- 사람 사이의 친구 관계
- 컴퓨터 사이의 연결
- 지하철역 사이의 노선
- 웹 페이지 사이의 링크
- 게임 맵에서 이동 가능한 방향
그래프 문제는 문제 설명에 Graph라는 단어가 직접 나오지 않아도 등장할 수 있습니다.
예를 들어 “컴퓨터들이 연결되어 있다”, “도시 사이에 길이 있다”, “A 작업 후 B 작업을 해야 한다”, “친구 관계가 주어진다” 같은 표현이 나오면 정점과 간선으로 바꿔 생각할 수 있습니다.
| 문제 표현 | 그래프 해석 |
|---|---|
| 컴퓨터들이 연결되어 있다 | 컴퓨터는 정점, 연결은 간선 |
| 도시 사이에 도로가 있다 | 도시는 정점, 도로는 간선 |
| 친구 관계가 주어진다 | 사람은 정점, 친구 관계는 간선 |
| 작업 순서가 주어진다 | 작업은 정점, 선후 관계는 방향 간선 |
| 칸 사이를 이동할 수 있다 | 칸은 정점, 이동 가능 여부는 간선 |
Graph 문제를 풀 때는 정점과 간선뿐만 아니라, 차수, 경로, 연결성, 사이클 같은 용어도 자주 등장합니다.
두 정점이 간선으로 직접 연결되어 있다면 두 정점은 인접하다고 표현합니다.
예를 들어 1번 정점과 2번 정점 사이에 간선이 있다면, 두 정점은 서로 인접한 정점입니다.
하나의 정점에 연결된 간선의 개수를 의미하고 무방향 그래프에서는 어떤 정점에 연결된 간선의 수를 그대로 차수라고 볼 수 있고, 방향 그래프에서는 들어오는 간선과 나가는 간선을 구분해서 봅니다.
| 구분 | 의미 |
|---|---|
| 진입 차수 | 해당 정점으로 들어오는 간선의 개수 |
| 진출 차수 | 해당 정점에서 밖으로 나가는 간선의 개수 |
한 정점에서 다른 정점까지 이동할 때 거치는 정점과 간선의 순서를 의미하고 두 정점 사이에 경로가 존재한다면 한 정점에서 다른 정점으로 이동할 수 있다고 볼 수 있습니다.
정점들이 서로 이어져 있는지를 나타내는 개념인데 그래프 안의 모든 정점 사이에 경로가 존재하면 연결 그래프라고 하고, 일부 정점이 분리되어 있으면 비연결 그래프라고 합니다.
어떤 정점에서 출발해 간선을 따라 이동하다가 다시 자기 자신으로 돌아오는 경로를 의미하고 사이클이 없는 그래프를 비순환 그래프라고 하며, 방향 그래프에서 사이클이 없는 구조는 방향성 비순환 그래프라고 부르기도 합니다.
그래프는 간선의 방향 여부, 비용 여부, 연결 구조에 따라 여러 종류로 나눌 수 있습니다.
간선에 방향이 존재하는 그래프입니다.
예를 들어 A -> B는 A에서 B로 갈 수 있다는 의미지만, 반대로 B에서 A로 갈 수 있다는 뜻은 아닙니다.
- 선수 과목 관계
- 작업 순서 관계
- 일방통행 도로
- 웹 페이지 링크
- 팔로우 관계
간선에 방향이 없는 그래프입니다.
예를 들어 A - B는 A에서 B로도 갈 수 있고, B에서 A로도 갈 수 있다는 의미입니다.
- 친구 관계
- 컴퓨터 연결 관계
- 양방향 도로
- 네트워크 연결 관계
- 같은 그룹에 속한 관계
간선마다 비용, 거리, 시간 같은 값이 존재하는 그래프이며 가중치 그래프에서는 단순히 연결되어 있는지뿐만 아니라, 어떤 연결을 선택했을 때 비용이 더 작은지까지 고려해야 합니다.
- 도시 사이의 이동 거리
- 도로 통행 시간
- 항공권 가격
- 네트워크 전송 비용
- 택배 배송 비용
간선마다 별도의 비용이 없는 그래프이기 때문에 연결 여부만 중요하며 모든 간선의 비용이 같다고 볼 수 있습니다.
- 친구 관계
- 컴퓨터 연결 여부
- 단순 이동 가능 여부
- 같은 그룹에 속하는지 여부
- 도달 가능 여부
모든 정점 사이에 경로가 존재하는 그래프이고 어떤 정점에서 시작하더라도 다른 모든 정점으로 이동할 수 있다면 연결 그래프라고 볼 수 있습니다.
일부 정점 사이에 경로가 존재하지 않는 그래프이기 때문에 그래프가 여러 개의 그룹으로 나뉘어 있으며 서로 다른 그룹 사이에는 이동할 수 없습니다.
모든 정점이 서로 직접 연결되어 있는 그래프이고 정점의 개수가 n개인 무방향 완전 그래프의 간선 개수는 다음과 같습니다.
n * (n - 1) / 2
기존 그래프의 일부 정점과 일부 간선으로 이루어진 그래프이며 전체 관계 중 일부 관계만 따로 떼어 보거나, 특정 조건을 만족하는 정점과 간선만 남길 때 부분 그래프 개념을 사용할 수 있습니다.
정점을 두 그룹으로 나누었을 때, 같은 그룹 안의 정점끼리는 연결되지 않고 서로 다른 그룹의 정점끼리만 연결되는 그래프입니다.
예를 들어 사람 그룹과 작업 그룹이 있고, 사람이 수행할 수 있는 작업에만 간선이 연결된다면 이분 그래프로 볼 수 있습니다.
방향 그래프이면서 사이클이 없는 그래프이고 작업 순서, 선수 과목, 빌드 순서처럼 어떤 일을 먼저 해야 하는 관계를 표현할 때 자주 등장합니다.
그래프는 보통 인접 행렬 또는 인접 리스트로 표현하는데 정점의 개수가 적고 두 정점의 연결 여부를 빠르게 확인해야 한다면 인접 행렬을 사용할 수 있고, 정점과 간선이 많으며 연결된 정점만 확인하면 된다면 인접 리스트를 사용하는 것이 효율적입니다.
인접 행렬은 2차원 배열을 사용하여 정점끼리 연결되어 있는지 나타내는 방식입니다.
graph[a][b] = 1
위와 같은 형태라면 a번 정점에서 b번 정점으로 갈 수 있다는 의미입니다.
- 구현이 직관적
- 두 정점의 연결 여부를
O(1)에 확인 가능 - 정점 개수가 많으면 메모리 사용량이 큼
- 간선이 적은 그래프에서는 비효율적
- 문제에서 연결 정보가 2차원 배열로 주어질 때 사용하기 쉬움
| 연산 | 시간복잡도 |
|---|---|
| 연결 여부 확인 | |
| 특정 정점과 연결된 모든 정점 확인 | |
| 전체 메모리 |
int[][] graph = new int[n + 1][n + 1];
graph[1][2] = 1;
graph[2][1] = 1;graph = [[0] * (n + 1) for _ in range(n + 1)]
graph[1][2] = 1
graph[2][1] = 1const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0))
graph[1][2] = 1
graph[2][1] = 1인접 리스트는 각 정점마다 연결된 정점 목록을 저장하는 방식입니다.
graph[1] = [2, 3]
위와 같은 형태라면 1번 정점은 2번, 3번 정점과 연결되어 있다는 의미입니다.
- 메모리를 효율적으로 사용
- 연결된 정점만 확인 가능
- 대부분의 코딩 테스트 그래프 문제에서 자주 사용
- 간선이 적은 그래프에 적합
- 정점과 간선의 개수가 클 때 인접 행렬보다 유리
| 연산 | 시간복잡도 |
|---|---|
| 연결 여부 확인 | |
| 특정 정점과 연결된 모든 정점 확인 | |
| 전체 메모리 |
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
graph.get(1).add(2);
graph.get(2).add(1);graph = [[] for _ in range(n + 1)]
graph[1].append(2)
graph[2].append(1)const graph = Array.from({ length: n + 1 }, () => [])
graph[1].push(2)
graph[2].push(1)| 구분 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 저장 방식 | 2차원 배열 | 리스트 배열 |
| 메모리 | ||
| 연결 여부 확인 | 빠름 | 상대적으로 느림 |
| 연결된 정점 확인 | 모든 정점을 확인해야 함 | 연결된 정점만 확인 |
| 적합한 경우 | 정점 수가 적거나 연결 여부 확인이 많을 때 | 정점 수와 간선 수가 많을 때 |
정점의 개수가 적고, 두 정점이 연결되어 있는지 자주 확인해야 한다면 인접 행렬이 편하고 문제에서 처음부터 2차원 배열 형태로 연결 정보가 주어진다면 인접 행렬을 그대로 활용할 수 있습니다.
정점과 간선의 개수가 많고, 특정 정점과 연결된 정점들만 확인하면 된다면 인접 리스트가 효율적입니다.
대부분의 코딩 테스트 그래프 문제에서는 메모리 효율 때문에 인접 리스트를 많이 사용합니다.
대부분 대상 사이의 연결 관계를 어떻게 해석할 것인지에 따라 해결 방향이 정해집니다.
여러 대상 사이의 연결 정보가 주어지고, 이를 그래프로 표현해야 하는 문제입니다.
-
n개의 도시와 도로 정보가 주어짐 -
n개의 컴퓨터와 연결 정보가 주어짐 - 사람 사이의 친구 관계가 주어짐
- 노드와 간선 정보가 배열로 주어짐
문제에 등장하는 대상을 정점으로 보고, 두 대상 사이의 관계를 간선으로 저장하고 이때 관계가 양방향인지 단방향인지 먼저 확인해야 하며, 양방향이라면 두 방향 모두 저장해야 합니다.
그래프 안에서 서로 연결된 정점들의 묶음을 다루는 문제입니다.
- 네트워크 개수 구하기
- 친구 그룹 개수 구하기
- 연결된 컴퓨터 그룹 수 구하기
- 서로 연결된 영역 구하기
그래프에서 하나의 묶음으로 이어진 정점들을 하나의 연결 요소로 볼 수 있는데 이런 문제에서는 전체 그래프가 하나로 연결되어 있는지, 아니면 여러 그룹으로 나뉘어 있는지 파악하는 것이 중요합니다.
두 정점 사이에 이동 가능한 경로가 존재하는지 확인하는 문제입니다.
- A에서 B까지 갈 수 있는지 확인
- 주어진 여행 경로가 가능한지 확인
- 특정 도시에서 다른 도시로 이동 가능한지 확인
- 두 사람이 관계망 안에서 연결되어 있는지 확인
두 정점이 같은 연결 요소 안에 있으면 경로가 존재한다고 볼 수 있습니다.
반대로 서로 다른 연결 요소에 있다면 중간에 이어지는 간선이 없으므로 이동할 수 없습니다.
어떤 작업을 먼저 해야 하고, 그 이후에 다른 작업을 해야 하는 관계가 주어지는 문제입니다.
- 선수 과목 문제
- 작업 순서 문제
- 빌드 순서 문제
- 조건을 만족하는 순서 찾기
작업을 정점으로 보고, 선후 관계를 방향 간선으로 표현하고 이런 문제는 보통 방향 그래프로 해석되며, 사이클이 존재하는지 또는 올바른 순서를 만들 수 있는지가 중요해집니다.
2차원 배열에서 각 칸을 정점으로 보고, 상하좌우로 이동 가능한 관계를 간선으로 해석하는 문제입니다.
- 지도 문제
- 미로 문제
- 게임 맵 문제
- 섬의 개수 문제
- 영역 구분 문제
각 칸을 하나의 정점으로 보고, 이동 가능한 인접 칸을 간선으로 생각하고 이때 배열의 범위를 벗어나지 않는지 확인해야 하며, 이동할 수 없는 칸은 간선이 없는 것으로 처리합니다.
프로그래머스 - 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
n개의 컴퓨터가 있고, 일부 컴퓨터들이 서로 연결되어 있을 때 네트워크의 개수를 구하는 문제입니다.
여기서 컴퓨터는 정점으로 볼 수 있고, 컴퓨터 사이의 연결 관계는 간선으로 볼 수 있습니다.
| n | computers | return |
|---|---|---|
| 3 | [[1,1,0],[1,1,0],[0,0,1]] |
2 |
| 3 | [[1,1,0],[1,1,1],[0,1,1]] |
1 |
이 문제에서 computers[i][j]가 1이면 i번 컴퓨터와 j번 컴퓨터가 연결되어 있다는 의미입니다.
즉, 입력 자체가 인접 행렬 형태로 주어졌다고 볼 수 있으며, 직접 연결되어 있지 않더라도 다른 컴퓨터를 거쳐 연결될 수 있다면 같은 네트워크에 속합니다.
첫 번째 예시는 다음과 같이 해석할 수 있습니다.
0번 컴퓨터 - 1번 컴퓨터
2번 컴퓨터
0번 컴퓨터와 1번 컴퓨터는 서로 연결되어 있으므로 하나의 네트워크이고, 2번 컴퓨터는 따로 떨어져 있으므로 또 다른 네트워크입니다.
따라서 전체 네트워크 개수는 2입니다.
두 번째 예시는 다음과 같이 해석할 수 있습니다.
0번 컴퓨터 - 1번 컴퓨터 - 2번 컴퓨터
0번 컴퓨터와 2번 컴퓨터가 직접 연결되어 있지 않더라도, 1번 컴퓨터를 통해 연결되어 있으므로 모두 하나의 네트워크에 속합니다.
따라서 전체 네트워크 개수는 1입니다.
이 문제는 Graph 파트에서는 특정 탐색 구현보다, 먼저 입력을 그래프로 해석하는 것이 중요합니다.
- 컴퓨터 하나하나를 정점으로 봅니다.
-
computers[i][j] == 1이면 두 컴퓨터 사이에 간선이 있다고 봅니다. - 직접 연결뿐만 아니라 간접 연결까지 같은 네트워크로 봅니다.
- 서로 연결된 컴퓨터 묶음의 개수를 구하는 문제로 해석합니다.
이 문제의 입력은 이미 인접 행렬 형태이지만, 간선 목록이 주어지는 문제라면 보통 아래처럼 인접 리스트로 바꿔서 표현할 수 있습니다.
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
graph.get(a).add(b);
graph.get(b).add(a);
}graph = [[] for _ in range(n + 1)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)const graph = Array.from({ length: n + 1 }, () => [])
for (const [a, b] of edges) {
graph[a].push(b)
graph[b].push(a)
}그래프 문제에서는 무엇을 정점으로 볼지, 무엇을 간선으로 볼지 먼저 정해야 합니다.
예를 들어 컴퓨터 네트워크 문제에서 컴퓨터는 정점이고, 컴퓨터 사이의 연결 정보는 간선입니다.
간선의 방향이 있는 문제인지 없는 문제인지 확인하지 않으면 그래프를 잘못 만들 수 있는데 특히 무방향 그래프인데 한쪽 방향만 저장하면 실제로는 연결되어 있는 정점을 찾지 못할 수 있습니다.
graph.get(a).add(b);graph.get(a).add(b);
graph.get(b).add(a);노드 번호가 1번부터 시작하는 문제에서는 배열이나 리스트의 크기를 n + 1로 잡는 경우가 많습니다.
반대로 노드 번호가 0번부터 시작하는 문제에서는 크기를 n으로 잡는 것이 자연스럽습니다.
정점 수가 큰데 인접 행렬을 사용하면 메모리 초과가 발생할 수 있습니다.
반대로 두 정점의 연결 여부를 자주 확인해야 하는 문제에서는 인접 행렬이 더 편할 수 있습니다.
인접 행렬 문제에서는 computers[i][i] = 1처럼 자기 자신과 연결되어 있다고 표시되는 경우가 있는데 이 값은 보통 네트워크 개수를 구할 때 큰 문제가 되지 않지만, 문제에 따라 자기 자신과의 연결을 간선으로 볼지 무시할지 확인해야 합니다.
그래프에서는 두 정점이 직접 연결되어 있지 않아도 중간 정점을 통해 이어질 수 있습니다.
예를 들어 A와 C가 직접 연결되어 있지 않더라도 A-B-C 형태로 이어져 있다면 A와 C는 같은 연결 요소에 속합니다.
작업 순서처럼 방향이 있는 관계에서는 사이클이 존재하면 올바른 순서를 만들 수 없는 경우가 있어서 순서 관계를 그래프로 해석할 때는 방향성과 함께 사이클 가능성도 같이 고려해야 합니다.
Graph 문제는 결국 대상 사이의 관계를 정점과 간선으로 바꿔 생각하는 것이 핵심입니다.
- 그래프는 정점과 간선으로 이루어진 비선형 자료 구조입니다.
- 문제의 대상은 정점으로 볼 수 있습니다.
- 대상 사이의 관계는 간선으로 볼 수 있습니다.
- 간선의 방향 여부에 따라 방향 그래프와 무방향 그래프로 나뉩니다.
- 간선의 비용 여부에 따라 가중치 그래프와 비가중치 그래프로 나뉩니다.
- 연결성, 사이클, 차수 같은 개념은 그래프 문제를 해석할 때 자주 사용됩니다.
- 그래프는 인접 행렬 또는 인접 리스트로 표현할 수 있습니다.
- 입력이 2차원 배열이면 인접 행렬로 볼 수 있고, 간선 목록이면 인접 리스트로 바꿔서 볼 수 있습니다.