2023. 04. 07.
이산수학에서의 그래프 📌
'그래프'라고 하면 원 그래프나 수학의 y=f(x) 그래프 등을 떠올리지만 컴퓨터 과학이나 이산수학에서 사용되는 '그래프'는 다음 그림과 같은 것이다.
그래프 구조
- 간선과 정점 존재 (간혹 가중치와 간선의 방향성 존재)
- 현실의 도시(정점)와 도시(정점)을 잇는 도로(간선) 도로 통행료(가중치)로 비유
- 현실의 지도를 선형적으로 표현하기 위해 고안된 구조
그림으로 보는 DFS와 BFS 차이점
DFS - 깊이 우선 탐색
DFS 는 시작점으로부터 지정한 정점에 도달하는 것이 목적이다. 정점을 탐색할 때 하나의 길을 끝까지 따라가며 더 이상 진행할 수 없는 곳에 다다르면 다음 후보가 되는 길을 따라간다.
# 인접 리스트 사용
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end= ' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# DFS 호출
dfs(graph, 1, visited)
BFS - 너비 우선 탐색
BFS 는 깊이 우선 탐색과 마찬가지로 그래프를 탐색하는 알고리즘이다. 최초 시점에 자신이 특정 정점에 있다고 하자. 목적은 시작점에서 간선을 따라가며 정점을 탐색하고 지정한 정점에 도달하는 것이다. 정점에 도착하면 해당 정점이 목표인지를 판단할 수 있다. 간단히 말해서 시작점에 가까운 정점부터 탐색하는 방식이다.
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)2023. 04. 07. 오늘의 문제풀이 ✍
BOJ 1012 - 유기농 배추
from collections import deque
import sys
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(graph, x, y):
queue = deque([(x,y)])
graph[x][y] = 0
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if graph[nx][ny] == 1 :
queue.append((nx,ny))
graph[nx][ny] = 0
test_case = int(input())
for i in range(test_case):
m,n,k = map(int,input().split())
graph = [[0] * n for _ in range(m)]
result = 0
for j in range(k):
x,y = map(int, input().split())
graph[x][y] = 1
for a in range(m):
for b in range(n):
if graph[a][b] == 1:
bfs(graph,a,b)
result += 1
print(result)BOJ 2667 - 단지번호 붙이기
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(graph, x, y):
n = len(graph)
queue = deque([(x,y)])
graph[x][y] = 0
cnt = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))
cnt += 1
return cnt
n = int(input())
graph = []
datas = []
for _ in range(n):
graph.append(list(map(int, input())))
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
datas.append(bfs(graph, i, j))
datas.sort()
print(len(datas))
for k in range(len(datas)):
print(datas[k])BOJ 7576 - 토마토
import sys
from collections import deque
input = sys.stdin.readline
m,n = map(int,input().split())
graph = []
result = 0
for i in range(n):
data = list(map(int,input().split()))
graph.append(data)
# 동 서 남 북
dx = [1,-1,0,0]
dy = [0,0,-1,1]
queue = deque()
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
queue.append((i,j))
def bfs(graph):
while queue:
x,y = queue.popleft()
for k in range(4):
nx,ny = dx[k] + x, dy[k] + y
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
bfs(graph)
for i in graph:
for tomato in i:
if tomato == 0:
print(-1)
exit()
result = max(result, max(i))
print(result-1)BOJ 10026 - 적록색약
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
graph = []
n = int(input())
visited = [[False] * n for _ in range(n)]
# 적록색약이 아닐 때 결과값, 적록색약일 때 결과값
result1 = 0
result2 = 0
for _ in range(n):
graph.append(list(input()))
def dfs(graph, x, y):
now = graph[x][y]
visited[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if visited[nx][ny] == False and graph[nx][ny] == now:
dfs(graph,nx,ny)
for a in range(n):
for b in range(n):
if visited[a][b] == False:
dfs(graph, a, b)
result1 += 1
# R - G 똑같이 만듬
for c in range(n):
for d in range(n):
if graph[c][d] == "G":
graph[c][d] = "R"
visited = [[False] * n for _ in range(n)]
for e in range(n):
for f in range(n):
if visited[e][f] == False:
dfs(graph, e, f)
result2 += 1
print(result1, result2)