[구름톤 챌린지] 3주차_작은 노드

 

필요한 개념

---

• 그래프

 

 

문제  분석

---

명시적인 형태의 그래프 문제이다.

그래프의 개념에 대해 이해하고 이를 어떻게 코드로 표현할 수 있는지 알아야 한다.

 

 

그래프

---

그래프는 어떤 정보 간의 연결 관계를 나타내는데 특화된 자료구조이다.

기본적인 형태의 그래프

그래프의 개념 자체는 단순하다.

그래프를 구성하는 필수적인 요소 두 가지는 정점이 있고, 정점 사이를 잇는 간선이 있다.

보통은 정점과 간선에 각종 조건들이 추가되어 다양한 상황을 추상화한다.

예시로는 특정 간선이 양방향이 아닌 단방향으로만 이동이 가능하도록 하거나, 정점을 방문하거나 간선을 이용할 때 비용을 추가하는 등의 경우가 있다.

컴퓨터의 네트워크나 도로망을 생각해보면 그래프가 어떤 느낌의 상황을 나타낼 수 있는지 알 수 있다.

 

 

그래프의 표현

---

그래프를 코드로 표현하는 핵심은 어떤 정점과 어떤 정점이 간선으로 연결되어 있는지를 잘 나타내는 것이다.

구현하는 방식은 크게 두 가지가 있다.

 

 

인접 행렬 (Adjacency Matrix)

인접 행렬은 어떤 두 정점이 연결되어 있는지를 2차원 배열을 이용해 나타내는 방식이다.

이 방식으로 그래프를 표현하기 위해서는 정점의 개수를 N 이라고 했을 때, N x N 크기의 배열이 필요하다.

기본적으로 배열에 있는 모든 칸의 초기값은 0이다.

배열의 r행 c열에 있는 칸의 값이 0이라는 것은 r번 정점에서 c번 정점으로 가는 간선이 존재하지 않는다는 의미이다.

그런 다음 a번 정점에서 b번 정점으로 가는 간선이 존재하는 경우 a행 b열에 해당하는 칸을 1로 바꿔준다.

1은 0과는 반대로 간선이 존재한다는 의미이다.

위에 있는 그래프를 인접 행렬을 이용해 표현하면 아래 그림처럼 표현할 수 있다.

0인 칸은 따로 표시하지 않고, 1인 칸만 표시했다.

위의 그래프는 양방향 그래프이기 때문에 a행 b열에 해당하는 칸과 b행 a열에 해당하는 칸이 모두 표시되었다.

이렇게 그래프를 표현했을 때의 장점은 어떤 정점과 어떤 정점이 연결되어 있는지를 빠르게 확인할 수 있다는 점이다.

a번 정점에서 b번 정점으로 가는 간선이 존재하는지 확인하려면, 단순히 배열의 a행 b열의 값이 0인지 1인지만 살펴보면 된다.

이 작업은 O(1), 즉 상수 시간에 해결할 수 있다.

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const MAX = 1004;
// 인접 행렬을 표시할 배열
let graph = Array(MAX).fill(null).map(() => Array(MAX).fill(0)); 
let input = [];
rl.on('line', (line) => {
    input .push(line);
});
rl.on('close', () => {
    // 정점과 간선의 개수 입력 받기
    const [_, M] = input[0].split(' ').map(Number);

    // 간선 정보 처리
    for (let i = 1; i <= M; i++) {
        // 간선이 연결하는 두 정점의 정보 입력 받기
        const [a, b] = inputLines[i].split(' ').map(Number);
        graph[a][b] = 1; // a -> b 간선이 존재한다는 의미
        graph[b][a] = 1; // 양방향 간선인 경우에는 b -> a 간선도 존재
    }
    console.log(graph);
});

 

하지만 우선 주어지는 정점 개수의 제곱에 비례하는 크기의 배열을 선언해야 하므로 공간 복잡도가 너무 크다.

• 주어지는 정점의 개수가 10^5개이면, 인접 행렬의 크기는 10^10 이다.
• int 자료형은 하나에 4 byte이므로, 정점의 개수가 $10^5$개일 때 인접 행렬을 저장하기 위해 필요한 메모리는 4 x 10^10 byte = 40 GB 이다.
• 일반적으로 문제를 풀 때 허용되는 메모리가 1GB를 넘지 않는다는 것을 생각해보면, 아무때나 사용 불가능하다는 것을 알 수 있다.

그리고 어떤 정점에 연결된 다른 정점의 정보를 알고자 할 때, 다른 N개의 정점에 대해 모두 살펴봐야 한다는 점이 불편하다.

• 위 그래프에서 6번 정점과 어떤 정점이 연결되어 있는지 알고 싶다고 하자.
• 6번 정점에 실제로 연결되어 있는 정점은 2번 정점 하나 뿐이지만, 1번부터 6번까지 모든 정점을 확인해보지 않고서는 어떤 정점들이 연결되어 있는지 알 수 없다.
• 즉, 인접한 정점의 정보를 알기 위해 O(N)의 시간을 투자해야 한다. 단 하나의 연결된 정점을 찾기 위해 많은 시간을 투자하는 건 낭비처럼 보일 수 있다.

 

인접 행렬은 그래프의 연결 관계를 직관적으로 나타내기는 좋지만 복잡도가 높다는 점에서 범용적으로 사용하기는 어렵다.

그래서 보통 알고리즘 문제를 해결할 때 그래프를 표현한다고 하면 인접 행렬 방식보다는 인접 리스트 방식을 주로 사용한다.

 

 

인접 리스트 (Adjacency List)

인접 리스트는 어떤 정점에서 간선으로 이동할 수 있는 정점만 관리하는 표현 방식이다.

구현할 때는 정점마다 이동할 수 있는 다른 정점의 개수가 다르므로 vector 와 같은 동적 배열을 이용한다.

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let graph = {};
let input = [];
rl.on('line', (line) => {
    input .push(line);
});

rl.on('close', () => {
    // 정점과 간선의 개수 입력 받기
    const [_, M] = input[0].split(' ').map(Number);

    // 간선 정보 처리
    for (let i = 1; i <= M; i++) {
        const [a, b] = input[i].split(' ').map(Number);
        // 객체의 Key가 없다면 초기화 해줌
        if (!graph[a]) {
            graph[a] = [];
        }
        if (!graph[b]) {
            graph[b] = [];
        }
        graph[a].push(b);
        graph[b].push(a);
    }
    console.log(graph);
});

 

인접 리스트는 각 정점 마다 실제로 연결되어 있는 정점의 정보만을 저장하기 때문에 공간 복잡도 측면에서 효율적이다.

실제로 어떤 정점이 연결되어 있는지를 찾기 위해서 N개의 정점을 모두 확인해보지 않아도 된다.

대신에 어떤 두 정점을 연결하는 간선이 존재하는지를 빠르게 확인할 수는 없다.

하지만 인접 행렬과 비교했을 때, 인접 리스트가 가지는 장점이 그래프 문제를 푸는 대부분의 경우에서 훨씬 강력하다.

 

 

그래프 탐색

---

그래프는 연결 관계를 표현하기 때문에 우리가 알아야할 것은 바로 그래프에서 탐색을 하는 방식이다.

그래프 탐색이란 간선을 따라서 그래프의 모든 정점을 방문하는 과정을 말한다.

다음에 방문할 정점의 순서를 어떻게 정하느냐에 따라서 다양한 그래프 탐색 방법이 있을 수 있지만, 대표적인 그래프 탐색 방법에는 DFS와 BFS가 있다.

 

 

문제 풀이

---

이번 문제는 DFS와 BFS와 같은 탐색 방식을 쓰지 않고, 문제에서 주어진 대로 구현하면 된다.

인접 리스트로 구현했다며나 어떤 정점에 인접한 정점 목록을 아래 코드처럼 탐색할 수 있다.

let G = {
    1: []  // 예를 들어, 여기에는 1번 정점과 인접한 정점들의 배열이 들어감
};

let cur = 1;

// cur과 인접한 정점은 G[cur]에 들어 있을테니, G[cur]의 값들을 순회
for (let next of G[cur]) {
    // Do Something
}

 

1. 그래프를 입력 받는다.
2. 현재 정점에서 인접한 정점 중, 아직 방문하지 않았으면서 가장 번호가 작은 정점을 찾는다.
3. 2에서 찾은 정점으로 이동한다.
4. 더 이상 이동할 수 없을 때까지 2, 3번 과정을 반복한다.
5. 방문한 정점의 개수와 마지막에 위치한 정점을 출력한다.

2~4번 과정의 구현이 중요한데, 더 이상 이동할 수 없을 때까지 반복해야 하니 아래 코드처럼 while문을 이용해서 구현할 수 있다.

let graph = {
    // 예시: 정점들과 각 정점에 인접한 정점들의 리스트
    // 1: [2, 3, 4],
    // 2: [1, 5],
    // ...
};

let visited = {};  // 방문 여부를 저장하는 객체
let cur = K; // 시작 정점
let ans = 0;

while (true) {
    let next = Infinity; // 다음으로 방문해야하는 정점 번호
    ans++; // 정점을 방문할 때마다 답을 1씩 증가시킴
		// 방문할 정점이 있다면, graph[cir] 을 순환하고, 아니라면 탐색하지 않음
    for (let n of (graph [cur] || [])) {
        if (visited[n]) continue;  // 방문한 정점이면 스킵
        next = Math.min(next, n);  // 가장 작은 정점의 번호를 다음 방문 정점으로 선택
    }
		// 방문할 수 있는 정점이 없는 경우이니, 반복문을 탈출
    if (next === Infinity) break; 
    cur = next;
    visited[cur] = true; // 방문 체크
}

 

 

그래프는 처음 접하는 개념이라 생소했지만, 그림과 매칭하면서 최대한 이해하려고 노력했다.

그래프를 구현하는 문제를 연습해봐야겠다..!