[알고리즘] 그래프란? & 탐색 알고리즘이란?

그래프란 무엇인가? (What)

정점(노드)들의 연결 관계를 간선(엣지)을 이용하여 표현한 자료구조

=> 그래프를 만든다는 것은 정점(node)과 간선(edge)을 정의하는 것

---

그래프는 언제 써야하는가? (Why)

자료구조이기 때문에 데이터를 저장하고 싶을 때 사용해야함. 

자료구조 - 선형 / 비선형이 있음.

비선형 자료구조 - 그래프, 트리가 있음. 

그래프는 트리와 달리 계층이 없고, 루프가 있을 수 있음. 

 

=> 따라서 자료구조를 쓰고 싶은데, 비선형이고 계층이 없고 루프가 있을 수 있는 구조가 적합할 때 ! 그래프를 사용하는 것이 좋음. 

---

그래프를 컴퓨터에 저장하는 방법 (How)

1. 인접 행렬

장점 - 구현이 쉬움, 연결되어 있는지 판단 빠름

단점 - 메모리 낭비가 많아짐 (노드 개수 ^ 2)

 

2. 인접 리스트 -> 탐색할 때 좋다! 

장점 - 메모리 효율적 저장 (양방향 리스트 : 간선 개수 * 2)

단점 - 연결되어 있는지 판단하는 것이 오래 걸림

---

탐색이란 무엇인가? (What)

한 노드를 기준으로, 간선을 따라 갈 수 있는 인접 노드를 조회하는 것. 

 

대표적인 2가지 탐색 방법

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

2. BFS (Breadth First Search 너비 우선 탐색)

 

---

탐색 알고리즘을 언제 쓰는가? (Why)

탐색의 목적은? 

데이터를 조회하는 것! 

 

간선이 가중치를 포함하지 않고, 노드 간의 연결 여부만 나타낼 때 .. ? 

노드에 중점을 둔 관점. 

---

어떻게 구현하는가? (How)

DFS

1. 최대한 깊이 들어가기 - 대부분 재귀함수로 구현 (스택과 관련 - 재귀함수를 호출하는 과정에서 스택 사용)

2. 방문여부 기록 - visited

 

<인접리스트 그래프 만들고  dfs 탐색하기>

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
cnt = 0


# 인접리스트 그래프 만들기
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(vertex): # vertex 현재 위치 인자
    global cnt
    for curr_v in graph[vertex]:
        if not visited[curr_v]:
            cnt += 1
            visited[curr_v] = True
            dfs(curr_v)

visited[1] = True
dfs(1)
print(cnt)

---

BFS

1. 인접한 노드부터 탐색 

2. queue 이용 - 탐색 가능한 정점 (있으면 반복 탐색, 없으면 탐색 종료)

 

<인접 리스트 구현 코드>

def bfs(): # n^2 시간복잡도
     while q:
        curr_v = q.popleft() #q에서 꺼낸 것 => current value
        for next_v in graph[curr_v]: # 1~n까지 수 중
            if not visited[next_v]: # 
                print(next_v)
                visited(next_v) = True
                q.append(next_v)

 

인접 리스트가 인접 행렬에 비해 연결된 모든 정점을 찾는 데(탐색)에는 이득임. 불필요한 탐색을 줄일 수 있음.

 

<bfs 탐색하기>

from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]


def in_range(r, c):
    return 0 <= r < n and 0 <= c < m

def bfs():
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nr, nc = r + dr, c + dc
            if in_range(nr, nc) and graph[nr][nc] == 1 and not visited[nr][nc]:
                #print(nr, nc)
                visited[nr][nc] = 1
                q.append((nr, nc))

q = deque()
visited[0][0] = 1
q.append((0, 0))

bfs()

print(visited[n - 1][m - 1])