Kim Jisong

I am an amazing person.

Graph

그래프는 다대다의 연결관계를 표현합니다. 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조입니다.

정점(Vertex) : 그래프의 구성요소로 하나의 연결점 인접 정점 : 두 개의 정점 간 간선이 존재하면 인접하다고 함 간선(Edge) : 두 정점을 연결하는 선 차수(Degree) : 정점 하나에 연결된 간선의 수 V 개의 정점을 갖는 그래프의 최대 간선의 수는 V * (V-1) / 2 (무향 그래프 - 양방향)

그래프 유형

무향 그래프(Undirected Graph) : 일방통행이 없는 양방향 그래프
유향 그래프, 방향 그래프(Directed Graph) : 하나의 간선이 하나의 방향만을 표현(화살표로 표현)
가중치 그래프(Weighted Graph) : 관계의 정도를 수치로 표현한 그래프 → 간선이 값을 갖고 있음
사이클 없는 유향, 방향 그래프(DAG, Directed Acyclic Graph) : 순환되지 않는 방향 그래프, 각 간선의 끝을 따라가면 원래의 정점으로 돌아오지 않음
완전 그래프 : 정점에 대해 가능한 모든 간선을 가진 그래프
부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
트리 : 싸이클 없는 무향 연결 그래프
두 정점 사이에 유일한 경로가 존재
하나의 루트 노드를 가짐
각 정점은 최대 하나의 부모노드만을 가짐
각 정점는 자식 정점(단말 노드)가 없거나 하나 이상 존재

경로

경로(Path)란 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것을 말합니다.

단순 경로 : 경로 중 정점을 최대 한 번만 지나는 경로
순환 경로
- 경로의 시작점과 끝점이 같음 또는
- 경로에서 어떤 정점을 2번이상 거치는 경우

그래프의 표현

인접 행렬(Adjacent matrix)
- 정점 중심
- V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장
  - 그래프가 가중치가 없다면 boolean 형으로 연결 정보를 표현
  - 가중치가 있다면 각 간선의 가중치를 배열로 저장
인접 리스트(Adjacent List)
- 정점 중심
- 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장(일반적 그래프)
간선 리스트(Edge List)
- 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

인접 행렬

V * V 정방 행렬
행 번호와 열 번호는 각 그래프의 정점에 대응
가중치가 없을 경우 연결정보만 저장, 가중치가 표현된다면 각 간선의 가중치를 표현

무향 그래프

i 번째 행의 합 = i 번째 열의 합 = Vi의 차수

유향 그래프

행 i 의 합 = Vi의 진출 차수( 나가는 경우 )
열 i 의 합 = Vi의 진입 차수( 들어오는 경우 )

인접 행렬의 단점

희소그래프
- 정점은 많지만 간선이 적은 그래프
- 각 정점의 몇 개 없는 간선을 표현하기 위해 큰 크기의 배열이 필요함
- 또한 각 정점의 탐색에서 모든 정점의 연결 경우를 탐색하기 위해 모든 행을 탐색하므로 시간복잡도 비효율
밀집 그래프
- 정점은 적지만 간선이 많은 그래프(ex 완전 그래프)
- 밀집 그래프를 표현하기 좋음

인접 리스트

각 정점에 대한 인접 정점들을 순차적으로 표현
하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장

무향 그래프

유향 그래프

그래프 탐색

너비우선탐색(BFS)

개념

너비우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다. 따라서 선입선출 형태의 큐 자료구조를 활용하여 만듭니다.

탐색의 과정 중 정점에 도착한 경로가 있을 때, 해당 경로는 시작 정점과 해당 정점에 대한 최단 경로입니다.

구현

from collections import deque
import sys
input = sys.stdin.readline

n, m, start = map(int, sys.stdin.readline().strip().split())
 
edge = [[] for _ in range(n + 1)]
 
for _ in range(m):
    v1, v2 = map(int, sys.stdin.readline().strip().split())
    edge[v1].append(v2)
    edge[v2].append(v1)
 
for e in edge:
    e.sort()

def bfs(x):
  queue = deque([start])
  b_check = [False for _ in range(n+1)]
  b_check[start] = True
  while queue:
    node = queue.popleft()
    if node not in edge:
      visit.append(node)
      queue.extend(graph[node])
  
  return visit

깊이우선탐색(DFS)

개념

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법입니다.

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 탐색하므로 후입선출 구조로 구현합니다. 메모리 스택을 활용한 재귀 함수, 혹은 직접 스택에 탐색 내용을 사용합니다.

구현

DFS 구현 (stack)

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

def dfs(graph, start_node):
  visit = list()
  stack = list()

  stack.append(start_node)

  while stack:
    node = stack.pop()
    if node not in visit:
      visit.append(node)
      stack.extend(graph[node])
  
  return visit

DFS 구현 (재귀)

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

# dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
#     visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
#     for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
#         if (visited[x] = NO) then dfs(V, E, x);
# }

N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort()

visit = [0]*(N+1)
cnt =  1
def dfs(R):
    global cnt
    visit[R] = cnt
    for x in graph[R]:
        if visit[x] == 0:
            cnt+=1
            dfs(x)

dfs(R)

for i in range(1,N+1):
    print(visit[i])

Example

https://www.acmicpc.net/step/24

주의) 파이썬의 기본 재귀 깊이 제한은 1000이므로 재귀문제를 활용할 때 아래와 같이 설정을 해두어야 에러메시지가 발생하지 않는다.

import sys
sys.setrecursionlimit(10 ** 6)

알고리즘 수업 - 깊이 우선 탐색 1

특이사항

무방향 그래프
깊이 우선 탐색
M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선
인접 정점은 오름차순으로 방문

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

# dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
#     visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
#     for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
#         if (visited[x] = NO) then dfs(V, E, x);
# }

N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort()

visit = [0]*(N+1)
cnt =  1
def dfs(R):
    global cnt
    visit[R] = cnt
    for x in graph[R]:
        if visit[x] == 0:
            cnt+=1
            dfs(x)

dfs(R)

for i in range(1,N+1):
    print(visit[i])

알고리즘 수업 - 깊이 우선 탐색 2

특이사항

무방향 그래프
깊이 우선 탐색
M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선
인접 정점은 내림차순으로 방문

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M, R = map(int,input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort(reverse=True)

visited = [0]*(N+1)
cnt = 1
def dfs(R):
    global cnt
    visited[R] = cnt
    for x in graph[R]:
        if visited[x] == 0:
            cnt += 1
            dfs(x)
dfs(R)

for i in range(1,len(visited)):
    print(visited[i])

알고리즘 수업 - 너비 우선 탐색 1

특이사항

무방향 그래프
너비 우선 탐색
M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선
인접 정점은 오름차순으로 방문

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, R = map(int,input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort()

cnt = 1
def dfs(R):
    global cnt
    visited = [0]*(N+1)
    visited[R] = cnt
    queue = deque([R])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if visited[v] == 0:
                cnt += 1
                visited[v] = cnt
                queue.extend([v])
    return visited

visited = dfs(R)

for i in range(1,len(visited)):
    print(visited[i])

알고리즘 수업 - 너비 우선 탐색 2

특이사항

무방향 그래프
너비 우선 탐색
M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선
인접 정점은 내림차순으로 방문

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, R = map(int, input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort(reverse=True)

cnt = 1
def bfs(R):
    global cnt
    visit = [0]*(N+1)
    visit[R] = cnt
    queue = deque([R])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if visit[v] == 0:
                cnt += 1
                visit[v] = cnt
                queue.extend([v])
    return visit

visit = bfs(R)

for i in range(1,len(visit)):
    print(visit[i])

바이러스

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input =  sys.stdin.readline

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 1
def search(R):
    global cnt
    visit = [0]*(N+1)
    visit[R] = cnt
    queue = deque([R])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if visit[v] == 0:
                cnt += 1
                visit[v] = cnt
                queue.extend([v])
    return visit

visit = search(1)

result = -1
for v in visit:
    if v != 0:
        result +=1
print(result)

DFS와 BFS

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, V = map(int,input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for g in graph:
    g.sort()

d_visit = [False]*(N+1)
d_search_list = []
def dfs(V):
    d_visit[V] = True
    d_search_list.append(V)
    for x in graph[V]:
        if d_visit[x] == False:
            dfs(x)

def bfs(V):
    visit = [False]*(N+1)
    visit[V] = True
    search_list = [V]
    queue = deque([V])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if visit[v] == False:
                visit[v] = True
                search_list.append(v)
                queue.extend([v])
    return search_list

dfs(V)
b_search_list = bfs(V)

d_output = ''
for d in d_search_list:
    d_output = d_output + str(d) + ' '
d_output = d_output[:-1]

b_output = ''
for b in b_search_list:
    b_output = b_output + str(b) + ' '
b_output = b_output[:-1]

print(d_output)
print(b_output)

단지 번호 붙이기

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

import sys
input = sys.stdin.readline

class searching():
    def __init__(self,maps):
        self._maps = maps
        self._count_house = []
        self._cnt = 0
    def _dfs(self,row,col):
        if row < 0 or row >= len(self._maps) or col < 0 or col >= len(self._maps[0]):
            return
        if self._maps[row][col] == '0':
            return
        self._maps[row][col] = '0'
        self._dfs(row-1,col)
        self._dfs(row+1,col)
        self._dfs(row,col-1)
        self._dfs(row,col+1)
        self._cnt += 1
    def search(self):
        for i in range(len(self._maps)):
            for j in range(len(self._maps[0])):
                  if self._maps[i][j] == '1':
                        self._cnt = 0
                        self._dfs(i,j)
                        self._count_house.append(self._cnt)
        return self._count_house

N = int(input())
maps = []
for _ in range(N):
    lists = []
    strings = input().rstrip("\n")
    for s in strings:
        lists.append(s)
    maps.append(lists)

func = searching(maps)
result = func.search()
result.sort()

print(len(result))
for r in result:
    print(r)

유기농 배추

땅의 모습이 아니라 배추의 위치가 주어지는 문제

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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

class searching():
    def __init__(self,map):
        self._map = map
        self._cnt = 0
    def _dfs(self,row,col):
        if row < 0 or row >= len(self._map) or col < 0 or col >= len(self._map[0]):
            return
        if self._map[row][col] == '0':
            return
        self._map[row][col] = '0'
        self._dfs(row-1,col)
        self._dfs(row+1,col)
        self._dfs(row,col-1)
        self._dfs(row,col+1)
    def search(self):
        for i in range(len(self._map)):
            for j in range(len(self._map[0])):
                if self._map[i][j] == '1':
                    self._cnt += 1
                    self._dfs(i,j)
        return self._cnt

T = int(input())

for _ in range(T):
    M, N, K = map(int,input().split())
    maps = [['0']*M for _ in range(N)]

    for _ in range(K):
        i, j = map(int,input().split())
        maps[j][i] = '1'
    
    func = searching(maps)
    print(func.search())

미로 탐색

BFS의 특징은 각 정점을 최단경로로 방문한다는 것입니다. 이 점을 활용해 최단거리를 구해 봅시다.

import sys
from collections import deque
input = sys.stdin.readline

class searching():
    def __init__(self,map):
        self._map = map
        self._cnt = 0
    def bfs(self,row,col):
        q = deque([(row,col,1)])
        while q:
            r, c, dist = q.popleft()
            # 도착
            if r == len(self._map)-1 and c == len(self._map[0])-1:
                break
            # 탐색
            if self._map[r][c] == '1':
                self._map[r][c] = '0'
                if r - 1 >= 0:                  q.extend([(r-1,c,dist+1)])
                if r + 1 < len(self._map):      q.extend([(r+1,c,dist+1)])
                if c - 1 >= 0:                  q.extend([(r,c-1,dist+1)])
                if c + 1 < len(self._map[0]):   q.extend([(r,c+1,dist+1)])
        return dist

N, M = map(int,input().split())
maps = []
for _ in range(N):
    lists = []
    string = input().rstrip("\n")
    for s in string:
        lists.append(s)
    maps.append(lists)

func = searching(maps)
print(func.bfs(0,0))

숨바꼭질

또 다른 BFS 최단거리 연습문제

import sys
from collections import deque
input = sys.stdin.readline

def bfs(n,k):
    q = deque([(n,0)])
    check = [0]*100001
    while q:
        point, time = q.popleft()
        # print(point,time)
        if point == k:
            break
        if check[point] == 0:
            check[point] = 1
            if point*2 < len(check):    q.extend([(point*2,time+1)])
            if point+1 < len(check):    q.extend([(point+1,time+1)])
            if point-1 >= 0:            q.extend([(point-1,time+1)])
    return time

N, K = map(int,input().split())
print(bfs(N,K))

Kim Jisong

Graph

Graph

그래프 유형

경로

그래프의 표현

인접 행렬

무향 그래프

유향 그래프

인접 행렬의 단점

인접 리스트

무향 그래프

유향 그래프

그래프 탐색

너비우선탐색(BFS)

개념

구현

깊이우선탐색(DFS)

개념

구현

Example

알고리즘 수업 - 깊이 우선 탐색 1

알고리즘 수업 - 깊이 우선 탐색 2

알고리즘 수업 - 너비 우선 탐색 1

알고리즘 수업 - 너비 우선 탐색 2

바이러스

DFS와 BFS

단지 번호 붙이기

유기농 배추

미로 탐색

숨바꼭질

나이트의 이동

토마토

토마토 …의 3차원 버전

뱀과 사다리 게임

이분 그래프

2022