2주차 - 그래프(백준 5567)

그래프

"정점(V, Vertex node)과 그 정점을 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조"
그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다.

• 정점(V): 어떤 자료나 개념을 표현하는 정점(노드)
• 간선(E): 정점을 연결
• 그래프 G(V, E): 정점들의 집합 V와 간선들의 집합 E로 구성된 그래프
• 경로: 한 정점인 시작점에서 다른 정점인 도착점으로 가는 간선이 연속되게 연결된 것
• 순환: 경로의 시작점과 도착점이 동일

인접(Adjacent): 간선 (U, V)에서, 두 정점 U와 V는 인접한다.
부속(Incident): 간선 (U, V)는 정점 U, 정점 V에 부속된다.

그래프의 종류

방향과 가중치에 따라 그래프의 종류를 구분할 수 있다.

가중치와 방향에 따른 그래프의 종류

그래프: 구현방법

인접 행렬
 : 인접 정점을 행렬로 표현

• 장점) 두 정점이 주어질 때 두 정점을 잇는 간선이 있는지를 한 번의 배열 접근만으로 확인 가능
• 단점) |V| x |V| 크기의 2차원 배열을 사용하기 때문에, 실제 간선의 개수와 관계없이 항상 O(|V^2|)크기의 공간을 사용한다는 문제점

인접 리스트
 : 인접 정점을 연결리스트로 표현
  *연결리스트: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료 구조

• 장점) |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어 있으므로, 전체 O(|V| + |E|)의 공간만을 사용함
• 단점) 두 정점이 주어질 때 이 정점이 연결되어 있는지를 알기 위해서는 연결 리스트를 일일이 뒤져야 함

 

그래프: 탐색방법

DFS(Deep First Search, 깊이 우선 탐색)
 : 시작 정점에서 시작해 다음 분기점으로 넘어가기 전에 해당 분기를 모두 탐색하는 방법

• 장점) 최선의 경우 가장 빠른 알고리즘
• 단점) 찾은 해가 최적이 아닐 가능성 O, 최악의 경우 해에 도달하는데 가장 오랜시간이 걸림

BFS(Breadth First Search, 너비 우선 탐색)
 : 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

• 장점) 최적해 보장 = 최단 경로를 보장
• 단점) 최소 실행 시간보다는 오래 걸림, 최악의 경우 실행에 가장 긴 시간이 걸릴 수 있음

---

백준 5567번 결혼식 문제

https://www.acmicpc.net/problem/5567

5567번: 결혼식

 

해당 문제를 그래프로 해석하자면, 상근이를 기준으로 상근이의 친구는 간선 길이=1, 친구의 친구는 간선 길이=2이다.
따라서 결혼식에 초대할 사람의 수는 간선 길이가 1, 2 인 노드의 개수이므로, 2번 이내로 탐색 가능한 노드 수를 구하면 된다. 
이때 1번은 자기 자신이므로 세지 않는다는 것을 유의해야한다.

#include <iostream>
using namespace std;

const int MAX = 501; // 최대 500명
int vector[MAX][MAX];
bool visited[MAX]; // 방문 여부
bool isFriend[MAX]; //상근이와 친구 여부
int number = 0; // 인원수

int main() {
    int n, m;
    cin >> n; // 동기의 수
    cin >> m; // 리스트의 길이

    for (int i = 0; i < m; i++){ // 입력받은 내용 적용
        int a, b;
        cin >> a >> b;
        vector[a][b] = 1;
        vector[b][a] = 1;
    }
    // 친구 배열
    for (int i = 2; i <= n; i++) {
        if (vector[1][i] == 1) {
            visited[i] = true; // 방문
            isFriend[i] = true; // 친구
        }
    }
    // 친구의 친구 배열
    for (int i = 2; i <= n; i++) {
        if (isFriend[i]) { // 친구 
            for (int j = 1; j <= n; j++) {
                if (vector[i][j]) { // 친구의 친구
                    visited[j] = true; // 방문
                }
            }
        }
    }
    // 초대 인원 계산
    for (int i = 2; i <= n; i++) {
        if (visited[i]) {
            number++;
        }
    }
    cout << number;
}

맞았습니다!!