BFS, DFS란? 🤔
그래프의 탐색 기법
목적 : 임의의 한 정점에서 시작하여 모든 정점을 방문
BFS : Bread First Search, 너비 우선 탐색
DFS : Depth First Search, 깊이 우선 탐색
구현 과정 📌
💡 BFS
간선의 모든 가중치가 같을 때, 최단 거리를 구하는 알고리즘
시작 정점을 기준으로 가까운 정점을 먼저 방문한다. (방문 순서 → 최단 거리에 영향)
큐를 이용한다 = 선입선출의 원칙으로 탐색한다.
def bfs(graph, start_node):
visit = list()
queue = list()
queue.append(start_node)
while queue:
node = queue.pop(0)
if node not in visit:
visit.append(node)
queue.extend(graph[node])
return visit(2~3) 방문했던 노드 목록을 차례대로 저장할 리스트와, 다음으로 방문할 노드의 목록을 차례대로 저장할 리스트를 만든다.
(5) 처음에는 시작 노드를 큐에 넣어준다.
(7) 큐에 더 이상 방문할 노드가 없을 때까지 loop를 돌려준다.
(8) 큐의 맨 앞에있는 노드를 꺼내온다.
(9) 해당 노드가 아직 방문 리스트에 없다면,
(10) 방문 리스트에 추가해주고,
(11) 해당 노드의 자식 노드들을 큐에 추가해준다.
💡 DFS
최단 거리가 아닐 수 있다
→ 최단 거리일 때 초기화 로직이 필요
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는 BFS와 거의 비슷하고, queue대신 stack을 사용한다는 점이 다르다.
💡 플러드 필
연결된 영역(연결 요소)가 몇 개인지 찾는 알고리즘
해결방법 📌
모든 정점(칸)에 대해 BFS 또는 DFS를 하되, 방문한 정점은 모두 체크해둔다.
만약 BFS할 정점이 체크되어 있으면 패스한다.
총 BFS를 한 횟수 = 연결된 영역(연결 요소)의 개수
기본 문제 📁
🪄 안전 영역
장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 한다.
어떤 지역의 높이 정보가 주어질 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 문제
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[*map(int, input().split())] for _ in range(n)]
ans = 1
for rain in range(1, 101):
visit = [[0] * n for _ in range(n)]
val = 0
for i in range(n):
for j in range(n):
if visit[i][j] == 0 and arr[i][j] > rain:
val += 1
visit[i][j] = 1
q = deque(); q.append([i, j])
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and arr[nx][ny] > rain:
visit[nx][ny] = 1
q.append([nx, ny])
ans = max(ans, val)
print(ans)🪄 연구소
0: 빈칸, 1: 벽, 2: 바이러스로 구성되어 있을 때
빈 칸에 벽을 3개 새로 세워 바이러스가 퍼질 수 없는 안전 영역의 최댓값을 구하는 문제
안전 영역이란 바이러스가 퍼진 후에 값이 0인 영역을 말한다.
from itertools import combinations as cb
from collections import deque
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
input = __import__('sys').stdin.readline
n, m = map(int, input().split())
arr = [[*map(int, input().split())] for _ in range(n)]
ans = 0
wall = []
virus = []
for i in range(n):
for j in range(m):
if arr[i][j] == 0: wall.append([i, j])
if arr[i][j] == 2: virus.append([i, j])
for w1, w2, w3 in cb(wall, 3):
visit = [[0] * m for _ in range(n)]
q = deque()
for x, y in [w1, w2, w3]:
arr[x][y] = 1
for x, y in virus:
q.append([x, y])
visit[x][y] = 1
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] != 1 and visit[nx][ny] == 0:
visit[nx][ny] = 1
q.append([nx, ny])
# val = sum(1 for i in range(n) for j in range(m) if arr[i][j] != 1 and visit[i][j] == 0)
val = 0
for i in range(n):
for j in range(m):
if arr[i][j] != 1 and visit[i][j] == 0:
val += 1
ans = max(ans, val)
for x, y in [w1, w2, w3]:
arr[x][y] = 0
print(ans)🪄 회사 문화 1
상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다.
내리 칭찬은 똑같은 값의 칭찬을 부하들도 받는다.
직속 상사와 직속 부하 관계가 주어지고, 칭찬에 대한 정보가 주어질 때 각자 얼마의 칭찬을 받았는지 출력하는 문제
def dfs(x):
for nx in adj[x]:
cost[nx] += cost[x]
dfs(nx)
import sys
sys.setrecursionlimit(100001)
input = __import__('sys').stdin.readline
n, m = map(int, input().split())
arr = [*map(int, input().split())]
adj = [[] for _ in range(n)]
cost = [0] * n
for i in range(1, n):
adj[arr[i] - 1].append(i)
for i in range(m):
x, w = map(int, input().split())
cost[x - 1] += w
dfs(0)
print(*cost)🧸💗 참고 블로그
