[Do it! 알고리즘 코딩테스트 - 자바 편] 09. 그래프

에지 리스트와 인접 리스트가 헷갈림: https://u-it.tistory.com/491

---

09. 그래프

그래프: 노드와 에지로 구성된 집합
- 노드: 데이터를 표현하는 단위
- 에지: 노드를 연결
(트리도 그래프의 일종)
 

09-1. 그래프의 표현

그래프를 구현하는 방법은 3가지.
 
1. 에지 리스트(edge list): "에지를 중심"으로 그래프를 표현.
- 배열에 "출발 노드, 도착 노드"를 저장하여 에지를 표현
- 또는 "출발 노드, 도착 노드, 가중치"를 저장하여 가중치가 있는 에지를 표현.
 
에지 리스트로 가중치 없는 그래프 표현하기
- 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현 -> 배열 열은 2개면 충분.
노드는 여러 자료형을 사용할 수 있는데 다음의 경우 노드는 Integer형.
방향 그래프: 1->2, 1->3, 2->4, 2->5, 3->4, 4->5
=> [[1, 2]], [1, 3], [2, 4], [2, 5], [4, 5]] = A[N][2]
 
이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.
그리고 노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라고 한다.
- 만약 방향이 없는 그래프라면 1<->2는 [1, 2], [2, 1]
 
에지 리스트로 가중치 있는 그래프 표현하기
가중치가 있는 그래프는 열을 3개로 늘려 3번째 열에 가중치를 저장하면 된다.
1->2로 향하는 가중치가 8인 에지는 이제 [1, 2, 8]로 표현된다.
[[1, 2, 8], [1, 3, 3], ...] = A[N][3]
 
에지 리스트는 구현하기 쉬운데 특정 노드와 관련되어있는 에지를 탐색하기는 지 않다.
에지 리스트는 벨만 포드나 크루스칼(MST) 알고리즘에 사용한다.
 
2. 인접 행렬(adjacency matrix)은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
노드 중심으로 그래프를 표현한다.
 
인접 행렬로 가중치 없는 그래프 표현하기
1~5번 노드가 각각 간선 가짐. 출발노드: 행, 도착노드: 열
x->y가 있으면 5*5 행렬에서 arr[x][y]=1로 설정
 
인접 행렬로 가중치 있는 그래프 표현하기
x-num->y가 있으면 5*5 행렬에서 arr[x][y]=가중치값num 으로 설정
 
인접 행렬을 이용한 그래프 구현은, 쉽고 두 노드를 연결하는 에지의 여부와 가중치값을 배열에 직접 접근해 바로 확인할 수 있는 게 장점.
하지만 노드와 관련되어있는 에지를 탐색하려면 N번 접근해야 하므로, 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
또한 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없음.
=> 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단해야 함
예를 들어 노드가 3만 개를 넘으면 자바 힙 스페이스 에러가 발생한다.
 
3.인접 리스트: 리스트 배열.
인접 리스트는 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언. 자료형은 경우에 맞게 사용.
ArrayList<Integer>[5]
- 인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
- 예를 들어 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2, 3]을 연결하는 방식으로 표현한다.
ArrayList<Integer>[N] = [1]->[2],[3]  [2]->[4],[5] ... 이런식
- 여기서도 방향이 있는 그래프를 표현한것
 
인접 리스트로 가중치 있는 그래프 표현하기
- 가중치가 있는 경우 자료형을 클래스로 사용한다.
(도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한다.
ArrayList<Node>[N] = [1]->[2,8],[3,3]  [2]->[4,4][5,15] ...
 
ArrayList[1]에 [(2,8), (3,3)]
노드 1과 2가 가중치 8 에지로, 노드 1과 3이 가중치 3 에지로 연결되어있다는 것을 보여줌. 방향성도 고려되어있음
인접리스트 구현은 복잡한 편이지만, 노드와 연결되어있는 에지를 탐색하는 시간이 매우 뛰어남
노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러 발생 X
이런 장점으로 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

---

[18352번: 특정 거리의 도시 찾기] / 실2
Java

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

public class Main {
    static List<Integer>[] graph;
    static int N, M, K, X;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            graph[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());
            graph[A].add(B); 
        }

        int[] dist = new int[N+1];
        Arrays.fill(dist, -1); // 방문 안 한 상태 초기화
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(X);
        dist[X] = 0;
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int next : graph[cur]){
                if(dist[next] == -1){ // 첫 방문일 때만
                    dist[next] = dist[cur] + 1;
                    q.add(next);
                }
            }
        }

        boolean printed = false;
        for(int i=1; i<=N; i++){
            if(dist[i] == K){
                System.out.println(i);
                printed = true;
            }
        }
        if(!printed) System.out.println(-1);
    }
}

 
C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dist[300001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k, x;
    cin >> n >> m >> k >> x;

    vector<vector<int>> graph(n+1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }

    // dist 초기화 (-1 = 미방문)
    fill(dist, dist+n+1, -1);

    queue<int> q;
    q.push(x);
    dist[x] = 0;

    // BFS
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int next : graph[curr]) {
            if (dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }

    bool found = false; // 1개라도 찾았는지 확인용
    // 오름차순 출력
    for (int i = 1; i <= n; i++) {
        if (dist[i] == k) {
            cout << i << "\n";
            found = true;
        }
    }
    if (!found) cout << -1;
}

 
 
[1325번: 효율적인 해킹] / 실1
Java

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

public class Main {
    static List<Integer>[] graph;
    static int N, M;
    static int[] count;
    static int[] visited;
    static int visitId = 1; // 현재 visited하는 번호

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        count = new int[N+1];
        visited = new int[N+1];

        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        
        // 방향: b -> a
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[b].add(a);
        }

        int max = 0;
        for (int i = 1; i <= N; i++) {
            count[i] = bfs(i);
            max = Math.max(max, count[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (count[i] == max) {
                sb.append(i).append(' ');
            }
        }
        System.out.println(sb);
    }

    static int bfs(int start) {
        visitId++;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        visited[start] = visitId;
        
        int cnt = 1;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int nxt : graph[cur]) {
                if (visited[nxt] != visitId) { // 이번에 아직 방문 안 했는지
                    visited[nxt] = visitId;
                    cnt++;
                    q.add(nxt);
                }
            }
        }
        return cnt;
    }
}

 
C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n+1);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        graph[b].push_back(a); // b로인해 a로 가는걸 확인해야
    }
    //BFS
    int maxCnt=0;
    vector<int> comp;
    for(int i=1; i<=n; i++){
        queue<int> q;
        bool visited[n+1]={};
        int cnt=0;
        
        q.push(i);
        visited[i]=true;
        while(!q.empty()){
            int c=q.front();
            q.pop();
            for(int j : graph[c]){
                if(!visited[j]){
                    cnt++;
                    visited[j]=true;
                    q.push(j);
                }
            }
        }
        if(maxCnt==cnt) {
            comp.push_back(i);
        } else if(maxCnt<cnt){
            maxCnt=max(maxCnt,cnt);
            comp.assign(1, i);
        }
    }
    for(int c : comp)
        cout<<c<<" ";
    return 0;
}

 
[1707번: 이분그래프] / 골4
Java

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

public class Main {
    static List<Integer>[] graph;
    static int[] color;
    static int V, E;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int K = Integer.parseInt(br.readLine());
        while (K-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            graph = new ArrayList[V + 1];
            for (int i = 1; i <= V; i++) 
                graph[i] = new ArrayList<>();
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph[a].add(b);
                graph[b].add(a);
            }
            color = new int[V+1]; // 0: 미방문, 1/-1: 두 그룹
            if (check()) sb.append("YES\n");
            else sb.append("NO\n");
        }
        System.out.print(sb.toString());
    }

    static boolean check() {
        for (int i = 1; i <= V; i++) {
            if (color[i] == 0) {
                if (!bfs(i)) {
                    return false;
                }
            }
        }
        return true;
    }

    static boolean bfs(int start) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        color[start] = 1;

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : graph[cur]) {
                if (color[next] == 0) {
                    color[next] = -color[cur]; // 반대 색으로 칠하기
                    q.add(next);
                } else {
                    if (color[next] == color[cur]) { // 이미 색이 있는데, 인접한 두 정점의 색이 같다면 이분 그래프 X
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

 
C++
오랜만에 풀어서 이분그래프 뜻을 까먹었었는데... 노드마다 두가지 색을 칠할 수 있는데, 연결된 것끼리는 다 색이 다르면 이분그래프.

 #include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool check(vector<vector<int>> graph, int v){
    int visited[v+1];
    fill(visited, visited+v+1, 0);
    
    for(int i=0; i<v; i++){
        queue<int> q;
        q.push(i);
        
        if(visited[i]==0) visited[i]=1;
        while(!q.empty()){
            int c=q.front();
            q.pop();
            for(int j : graph[c]){
                if(visited[j]==0) {
                    q.push(j);
                    visited[j]=3-visited[c];
                }if(visited[j]==visited[c]) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tk, v, e;
    cin>>tk;
    while(tk-->0){
        cin>>v>>e;
        vector<vector<int>> graph(v+1);
        for(int i=0; i<e; i++){
            int a, b;
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        if(check(graph, v))
            cout<<"YES\n";
        else    
            cout<<"NO\n";
    }
}

 
 
 
유니온파인드
 
 
[1717]
 
 
[1976]
 
[1043]
 
 

 
위상 정렬 (Topological Sort)

방향 그래프에서 노드들을 선후관계를 지키면서 일렬로 나열하는 것
[과목 수강] 수학 → 물리 → 양자역학, 수학 → 통계. "위상 정렬 결과: 수학 → 물리 → 통계 → 양자역학"
순서. 줄세우기. 하면 위상정렬.
진입차수(indegree): 어떤 노드로 들어오는 간선의 수. (진입차수 0 = 선행 조건 없음 = 지금 당장 처리 가능)
 
알고리즘 동작 (BFS 방식)
1. 모든 노드의 진입차수 계산 (a->b면 v[a].push_back(b))
2. 진입차수 == 0인 노드를 큐에 삽입
3. 큐에서 노드를 꺼내 출력
4. 해당 노드의 이웃 노드들의 진입차수 -1
5. 진입차수가 0이 된 노드를 큐에 삽입
6. 큐가 빌 때까지 반복
 
DFS로도 할 수 있는데 BFS가 더 좋음. 아래는 DFS... 

DFS로 끝까지 내려간 뒤
스택에 쌓고 역순 출력
void dfs(int x){
    visited[x] = true;
    for(int nxt : graph[x]){
        if(!visited[nxt]) dfs(nxt);
    }
    stk.push(x); // 끝난 뒤 push
}
→ 마지막에 스택 pop하면 위상정렬

dfs(1)
  dfs(2)
    dfs(4)
      갈 곳 없음 → stack push(4)
    stack push(2)
  dfs(3)
    4는 이미 visited
    stack push(3)
  stack push(1)

stack: [1, 3, 2, 4] (top이 1)
출력:    1  3  2  4

 
중요한 조건

• DAG (Directed Acyclic Graph) 에서만 가능
• 사이클이 있으면 위상 정렬 불가 (큐가 비었는데 출력한 노드 수 < 전체 노드 수 → 사이클 존재)

사이클 어떻게 감지?
BFS는 if (출력한 노드 수 != n) {  cout << "사이클 존재"; } 면 사이클 있음. 사이클 유무만 판단 가능.
DFS는 vector<int> state(n + 1, 0); 로 미방문했었으면 state[nxt]=0, 방문 중이면 state[nxt]=1, 완료했으면 state[nxt]=2로 체크.
사이클 경로를 추적할 수 있다.

void printCycle(int start, int cur) {
    vector<int> cycle;
    cycle.push_back(cur);
    
    while (cur != start) {  // 시작점 만나면 종료
        cur = parent[cur];
        cycle.push_back(cur);
    }
    reverse(cycle.begin(), cycle.end()); // 가장 부모부터 출력위해
    for (int node : cycle) cout << node << ' ';
}

void dfs(int cur) {
    state[cur] = 1;
    for (int nxt : graph[cur]) {
        if (state[nxt] == 1) {
            printCycle(nxt, cur);  // nxt가 사이클 시작점
            return;
        }
        if (state[nxt] == 0) {
            parent[nxt] = cur;
            dfs(nxt);
        }
    }
    state[cur] = 2;
}

 
 
 
다익스트라
 
 
벨만포드
 
플로이드워셜
 
최소신장트리