Graph / DFS / BFS

Graph

그래프는 여러 노드들이 개수 제한 없이 서로 연결된 상태를 말하며,

각 노드들은 계층구조를 갖지 않는다

트리는 그래프의 한 모델이지만 다음과 같은 차이를 보인다.

 

Graph	Tree
비순환 or 순환 방식 directed or undirected 네트워크 모델	비순환 방식 항상 directed 계층 모델

 

 

그래프는 다음과 같이 크게 세 종류로 나뉜다.

• 방향 그래프 (Directed graph)
• 무방향 그래프 (Undirected graph)
• 가중 그래프 (Weighted graph)
  - 이 경우 ( _ , 가중치) 형태로 행렬 or 리스트에 저장한다.

 

Graph representation

그래프를 구현하는 방법에는 두 가지가 있다. 

• 인접 행렬 (Adjacency Matrix) 
  두 vertex의 연결 여부, 즉 edge의 존재 여부를 표현한다. 
• 인접 리스트 (Adjacency List)
  각각의 vertex에 대한 인접 vertex들을 linked list로 표현한다.

인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
구현이 쉬움. Edge[i][j]->특정 노드 연결 여부 탐색, 수정 시간이 O(1)로 매우 빠름 노드의 수가 커질 수록 필요 메모리가 매우 커지고 낭비도 커짐	실제 데이터들만 저장하므로, 메모리 낭비를 최소화할 수 있다. 특정 노드 연결에 대해 탐색 시간이 최대 O(n)으로 오래 걸릴 수 있음

 

 

graph_representation.py

# 인접 행렬
adjacencyMatrix = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]

# 인접 리스트
adjacencyList = [[] for _ in range (3)] # 2차원 배열 선언
adjacencyList[0].append(1)
adjacencyList[0].append(2)
adjacencyList[1].append(0)
adjacencyList[2].append(0)

# 원소가 1부터 시작한다면 0번째 칸 비우는 것 주의

 

 

 

---

 

DFS (Depth First Search, 깊이 우선 탐색)

DFS와 BFS는 모든 노드를 검사하는 그래프 완전 탐색 방법이다. 

그 중 DFS는 현재 탐색하고 있는 경로를 끝까지 탐색한 후, 그 다음 경로를 탐색하는 것을 의미한다.

경로를 끝까지 탐색한 후 더 이상 갈 수 없을 때 이전 노드로 돌아가(back tracking) 방문하지 않은 노드에 대해 탐색한다.

*시간 복잡도 : 인접 행렬 O(n²) / 인접 리스트 O(n+e)

(*why? 인접 리스트에서 DFS가 n번 호출되긴 하지만 인접행렬과는 달리 DFS하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하므로 예측이 어려움. 하지만 DFS가 다 끝난 후를 생각하면, 모든 정점을 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 할 수 있으므로 O(n+e)의 시간이 걸렸다고 할 수 있음. 반면 인접 행렬에서는 정점마다 항상 n번씩 방문)

 

    

크게 다음과 같은 순으로 진행된다.

1. 스택의 최상단 노드 확인
2. 최상단 노드에게 방문하지 않은 인접 노드 있다면, 그 노드를 스택에 넣고 방문 처리 (=> 1. 해당 노드의 자식 노드를 스택에 넣고),
   방문하지 않은 인접 노드 없으면 스택에서 최상단 노드를 뺌 (=>2. 뺀 노드 출력, 3. 스택에서 꺼낸 노드의 자식 노드를 다시 스택에 추가)
   
3. 1,2를 반복 수행

위의 원리를 이용하여 재귀함수로 구현할 수 있다.

 

재귀함수

함수 호출이 반복적으로 일어날 때 가장 마지막에 호출된 함수가 수행되어야 그 전의 함수 호출이 종료되기 때문에, 재귀함수는 내부적으로 스택 자료구조와 동일하다. 따라서 스택 자료구조를 활용해야 하는 다수의 알고리즘은 재귀함수를 이용해 구현될 수 있다. 그 중 DFS가 대표적인 예이다.

 

 

 

재귀, 인접행렬를 이용한 구현.c

#include <stdio.h>

int graph[11][11];       //인접 행렬로 구현한 그래프 (1~10노드 이용)
int visited[11];         //방문 여부 확인

int DFS(int cur, int n){
    int i;
    visited[cur] = 1;   //시작 노드를 방문으로 체크
    for(i=1; i<=n; i++){
        if(graph[cur][i] == 1 && visited[i] == 0){ 
            //현재 노드에 인접하면서 방문하지 않은 노드일 시
            printf("%d ", i);
            DFS(i, n); //해당 인접 노드에서 그것의 인접 노드 계속 탐색(DFS)
        }
    }
}

 

 

재귀, 인접리스트를 이용한 구현.py

def DFS(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    for i in graph[start]: 		# v번째 리스트 내부 조사, 즉 v노드의 인접 노드 조사
        if not visited[i]:
            DFS(graph, i, visited) # 방문하지 않은 경우 (다음 노드 방문 처리 + 해당 인접 노드 탐색 진행) ...

활용

- 모든 경우를 조사하는 완전 탐색

- 순열 조합 구현

 

---

 

BFS (Breath First Search, 너비우선 탐색)

DFS와 마찬가지로 모든 노드를 검사하는 그래프 완전 탐색 방법이다. 

시작 노드로부터 length가 낮은 것부터, 즉 가까운 노드부터 탐색하는 알고리즘이다.

인접한 노드들을 큐에 넣고 가장 먼저 들어온 것부터 꺼내 해당 노드의 인접 노드를 검사하고, 큐의 순서에 따라 이를 반복한다.

큐(queue)를 이용하여 구현한다.

*시간 복잡도 : 인접 행렬 O(n²) / 인접 리스트 O(n+e) - 위의 논리와 같음

 

크게 다음과 같은 순으로 진행된다.

1. 시작 노드를 큐에 삽입하고 이를 방문 처리
2. 큐에서 하나의 노드를 꺼냄
3. 꺼낸 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고 방문 처리, 차례대로 큐에 삽입
   (큐에 넣은 노드는 방문 처리된 노드들, 이후 FIFO 방식으로 인접노드들 검사됨)
4. 2,3을 반복 수행

-> 핵심은 인접 노드 (그 중 방문하지 않은 노드)를 queue에 넣고, queue의 요소들이 존재할 때까지 노드들을 하나씩 꺼내며 검사한다!

 

 

# 키워드

✔️ 방문처리

✔️ queue 가 존재할때까지 하나씩 빼며

✔️ 문제의 조건에 만족하도록 인접한 것 queue에 append!

 

큐, 인접리스트를 이용한 구현.py

from collections import deque

def BFS(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:				# 큐가 빌 때까지 반복
        v = queue.popleft()		# 큐에서 원소를 뽑고
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:	# 뽑은 원소 인접 노드 탐색, 방문하지 않은 것들 큐에 삽입
                queue.append(i)
                visited[i] = True	# 이후 큐에 들어있는 다음 노드들 진행

활용

- depth를 계산해야 하는 문제

- 가중치 그래프에서 최단 거리 찾기 

---

연습 문제

백준 #1260 DFS와 BFS    

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

 

1260.py

from collections import deque

def DFS(start):
    visited[start] = True
    print(start, end=' ')
    for i in graph[start]:
        if not visited[i]:
            DFS(i)

def BFS(start):
    queue = deque([start])
    visited_2[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited_2[i]:
                queue.append(i)
                visited_2[i] = True
            
n, m, v = map(int, input().split())

# 인접 리스트
graph = [[] for _ in range (n+1)]
visited = [False] * (n+1)
visited_2 = [False] * (n+1)

for _ in range (m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()
# *** 큰 순으로 진행하기 위해 그래프를 정렬하여 오름차순임을 보장하기

DFS(v)
print()
BFS(v)

 

 

연습 문제 

백준 #13565 침투

DFS, node.js

스택 사용한 DFS

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

 

13565.js

const data = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [m, n] = data[0].split(' ').map(x=>parseInt(x));

const matrix = Array.from({ length : m }, () => Array(n).fill());

for(let i = 1; i < m + 1; i++){
    matrix[i - 1] = data[i].split('').map(x=>parseInt(x));
}

const dx = [-1, 1, 0, 0];
const dy = [0, 0, 1, -1];

function DFS(row, col, visited, stack){
    stack.push([row, col]);

    while(stack.length){
        let [row, col] = stack.pop();
        visited[row][col] = true;

        if(row == m - 1){
            return 1; 
        }

        for(let i = 0; i < 4; i++){
            if(0 <= row + dy[i] && row + dy[i] < m && 0 <= col + dx[i] && col + dx[i]< n){
                if(!visited[row + dy[i]][col + dx[i]]
                    && matrix[row + dy[i]][col + dx[i]] === 0){
                    stack.push([row + dy[i], col + dx[i]]);
                }
            }
        }
    }
    return 0;
}

let flag = 0;
const visited = Array.from({ length : m }, () => Array(n).fill(false));

for(let i = 0; i < n; i++){
    if(matrix[0][i] === 0 && !visited[0][i]){
        if(DFS(0, i, visited, [])){
            flag = 1;
            break;
        }
    }
}

console.log(flag ? 'YES' : 'NO');