6. 그래프, 그래프 탐색

- 그래프

- DFS

- BFS

 

정점(vertex):그래프를 구성하는 개체(점)=노드

간선(edge): 정점과 정점을 연결하는 선

그래프(gragh): 정점과 간선으로 구성된 자료구조

방향그래프(directed graph): 간선에 방향이 있는 그래프   cf. 양방향 그래프(undirected graph). 그냥 그래프와 같다.

차수(degree): 정점에 연결된 간선의 수

방향 그래프에서는 정점으로 들어오는 간선과 나가는 간선을 indgree, outdegree로 구분.

경로(path): 정점을 중복해서 지나지 않는 간선의 나열

사이클: 시작 정점과 끝 정점이 같은 경로

방향 그래프에서 사이클을 판단할 때는 방향을 고려해야한다.

순환 그래프(cyclic graph)

비순환 그래프(acyclic graph)

 

그래프는 두 정점 사이의 관계집합이라 할 수 있다.

그래프를 표현할 때는 두 정점 사이의 관계를 저장하자.

 

그래프의 표현에는 2가지가 있다.

인접 행렬

인접 리스트

 

인접 행렬 vs 인접 리스트
두 정점의 연결 확인                  O(1)   O(degree(V))
한 정점과 연결된 정점 확인      O(V)    O(degree(V))
필요한 메모리 크기 (공간 복잡도)  O(V²)     O(V+E)

 

보통은 인접리스트를 많이 사용한다.

 

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

인접 행렬과 인접 리스트로 나타내보기

 

5 4 1
1 2
1 3
3 4
4 5

#인접 행렬
n, m, start = map(int, input().split())
graph = [[0] * (n+1) for _ in range(n+1)]

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

for i in range(1, n+1):
    print(*graph[i][1:])

0 1 1 0 0
1 0 0 0 0
1 0 0 1 0
0 0 1 0 1
0 0 0 1 0

#인접 그래프
n, m, start = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

for i in range(1, n + 1):
    print(*graph[i])

2 3
1
1 4
3 5
4

 

그럼 그래프를 탐색해보자.

dfs(depth first search) 깊이 우선 탐색

n = 7  # 노드 개수
graph = [[] for _ in range(n+1)]

graph[1] = [2, 3]
graph[2] = [1, 4, 5]
graph[3] = [1, 6, 7]
graph[4] = [2]
graph[5] = [2]
graph[6] = [3]
graph[7] = [3]

visit = [False] * (n+1)  # 방문 여부 리스트

def dfs(node):
    print(node, end=' ')
    for conn_node in graph[node]:
        if not visit[conn_node]:
            visit[conn_node] = True
            dfs(conn_node)

visit[2] = True
dfs(2)

 

bfs(breadth first search) 너비 우선 탐색

큐를 이용해 구현한다.

def bfs(node):
    d.append(node)#시작노드
    visit[node] = True  # 큐에 노드를 추가할 때 방문 체크
    while d:#큐에 값이 있을 때까지 돈다.
        now_node = d.popleft()#큐에서 꺼내고 탐색
        print(now_node)
        for conn_node in graph[now_node]:#인접노드 가져옴
            if not visit[conn_node]:
                d.append(conn_node)
                visit[conn_node] = True  # 큐에 노드를 추가할 때 방문 체크

 

정답코드

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

for i in range(n+1):
    graph[i].sort()#순서대로 방문

visit = [False] * (n+1)
visit[start] = True
dfs(start)
print()

visit = [False] * (n+1)
bfs(start)

 

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

이차원 배열을 그래프라고 생각. 각각의 칸이 정점

이차원 배열을 돌며 아직 방문하지 않은 1을 만나면 새로운 단지로 추가

n = int(input())
graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]
visit = [[False for _ in range(n)] for _ in range(n)]
count = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and not visit[i][j]:
            visit[i][j] = True
            d = deque()
            d.append((i, j))
            now_count = 1#현재 단지 크기

            # BFS
            while d:
                now_i, now_j = d.popleft()

                next_i, next_j = now_i + 1, now_j  # 아래 방향
                if 0 <= next_i < n and 0 <= next_j < n:#범위체크
                    if graph[next_i][next_j] == 1 and not visit[next_i][next_j]:
                        visit[next_i][next_j] = True
                        d.append((next_i, next_j))
                        now_count += 1

                next_i, next_j = now_i - 1, now_j  # 위 방향
                if 0 <= next_i < n and 0 <= next_j < n:
                    if graph[next_i][next_j] == 1 and not visit[next_i][next_j]:
                        visit[next_i][next_j] = True
                        d.append((next_i, next_j))
                        now_count += 1

                next_i, next_j = now_i, now_j + 1  # 오른쪽 방향
                if 0 <= next_i < n and 0 <= next_j < n:
                    if graph[next_i][next_j] == 1 and not visit[next_i][next_j]:
                        visit[next_i][next_j] = True
                        d.append((next_i, next_j))
                        now_count += 1

                next_i, next_j = now_i, now_j - 1  # 왼쪽 방향
                if 0 <= next_i < n and 0 <= next_j < n:
                    if graph[next_i][next_j] == 1 and not visit[next_i][next_j]:
                        visit[next_i][next_j] = True
                        d.append((next_i, next_j))
                        now_count += 1

            count.append(now_count)

print(len(count))
for c in sorted(count):
    print(c)

 

 

중복코드 개선

(1, 0) (-1, 0) (0, 1) (0, -1) 쌍을 미리 만들어 두고 반복문을 돌리자.

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

di = [1, -1, 0, 0]
dj = [0, 0, 1, -1]

n = int(input())
graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]
visit = [[False for _ in range(n)] for _ in range(n)]
count = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and not visit[i][j]:
            visit[i][j] = True
            d = deque()
            d.append((i, j))
            now_count = 1

            # BFS
            while d:
                now_i, now_j = d.popleft()

                for k in range(4):
                    next_i, next_j = now_i + di[k], now_j + dj[k]
                    if 0 <= next_i < n and 0 <= next_j < n:
                        if graph[next_i][next_j] == 1 and not visit[next_i][next_j]:
                            visit[next_i][next_j] = True
                            d.append((next_i, next_j))
                            now_count += 1

            count.append(now_count)

print(len(count))
for c in sorted(count):
    print(c)

 

 

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

자연스럽게 BFS 떠올릴 수 있다.

모든 익은 토마토를 큐에 담아두고 BFS 알고리즘을 적용

d = deque()

d.append((i, j, 0))  # 0은 현재 날짜

# BFS
while d:
    now_i, now_j, now_date = d.popleft()

    for k in range(4):
        next_i, next_j = now_i + di[k], now_j + dj[k]
        if 0 <= next_i < n and 0 <= next_j < n:
            if graph[next_i][next_j] == 0:
                graph[next_i][next_j] = 1
                d.append((next_i, next_j, now_date + 1))