너비우선탐색을 어떤 문제에 어떻게 적용하는지에 대해서 배우게 됩니다.
기본개념
🟢네 방향 탈출 가능 여부 판별하기
✏️BFS, 너비 우선 탐색
- 시작점을 기준으로 가장 가까운 곳부터 순서대로 탐색을 진행하는 방식
- 재귀함수 없이 queue 자료구조 이용
✏️그래프 상에서의 BFS 탐색
DFS 탐색 방법
- 새로 방문하게 되는 위치가 생기면 해당 위치를 DFS함수의 인자로 넘긴다.
- 재귀함수를 호출해 탐색을 재개한다.
BFS 탐색 방법
- queue를 이용해 지금까지 방문한 노드들을 관리
- 새로 방문하게 되는 노드를 queue에 계속 넣어준다.
- queue가 empty 상태가 되기 전까지, 즉 queue가 비워지기 전 까지 queue에서 가장 앞에 있는 원소를 pop한다.
- 해당 원소를 현재 원소의 위치로 설정한다.
- 이 위치를 기준으로 연결된 지점들에 대한 탐색을 진행한다.
- DFS : 재귀함수로 새로 찾은 노드를 넘긴다.
BFS : 새로 찾은 노드를 큐에 추가하고 탐색을 유지하기 위해 queue가 비워질 때까지 계속 진행한다.
# DFS
def dfs(vertex):
for curr_v in range(1, n + 1):
if graph[vertex][curr_v] and not visited[curr_v]:
print(curr_v)
visited[curr_v] = True
dfs(curr_v)
root_vertex = 1
print(root_vertex)
visited[root_vertex] = True
dfs(root_vertex) # BFS
def bfs():
while q:
curr_v = q.popleft()
for next_v in range(1, n + 1):
if graph[curr_v][next_v] and not visited[next_v]:
print(next_v)
visited[next_v] = True
q.append(next_v)
root_vertex = 1
print(root_vertex)
visited[root_vertex] = True
q.append(root_vertex)
bfs()✏️그래프 탐색 알고리즘의 대원칙
- 시작점으로부터 연결된 모든 정점을 전부 방문해야 한다.
- 이미 방문한 정점은 다시 방문하지 않는다.
⇒ 정점의 개수만큼의 크기를 갖는 visited 리스트를 만들어 방문한 위치와 방문하지 않은 위치 저장해야 한다.
BFS에서는 queue에 새로운 위치를 넣어주는 순간에 해당 위치의 visited 값을 True로 변경한다.
✏️인접 행렬과 인접 리스트
인접 행렬 이용
def dfs():
while q:
curr_v = q.popleft()
for next_v in range(1, n + 1):
if graph[curr_v][next_v] and not visited[next_v]:
print(next_v)
visited[next_v] = True
q.append(next_v)인접 리스트 이용
def dfs():
while q:
curr_v = q.popleft()
for next_v in graph[curr_v]:
if not visited[next_v]:
print(next_v)
visited[next_v] = True
q.append(next_v)✏️격자에서의 BFS 탐색
- 일반적인 그래프에서 두 정점의 연결관계 표현 = 인접 행렬 또는 인접 리스트
- 2차원 격자에서는 일반적으로 인접한 곳으로만 이동이 가능하므로, 인접 행렬이나 인접 리스트를 만들 필요가 없다.
그래프에서의 BFS 탐색
- queue 필요
- queue에 각 노드의 위치를 넣어야 한다.
격자에서의 BFS 탐색
-
현재 위치 표현을 위해 행렬에서의 x행 y열을 의미하는 (x, y) 2개의 값이 반드시 필요
⇒ visited 배열 역시 2차원이 되어야 함, 0번지부터 사용하면 시작 위치가 (0, 0) -
visit 체크를 하고, queue에 원소를 넣는 과정을 진행하는 함수 push를 정의하여 이용하면 깔끔하게 코드 작성 가능
def push(x, y):
global order
answer[x][y] = order
order += 1
visited[x][y] = True
q.append((x, y))
push(0, 0)
bfs()- 현재 queue에서 가장 앞에 있는 원소를 현재 위치로 설정, queue에서 해당 원소를 pop 해줘야 한다.
BFS 함수에서는 현재 위치 (x, y)로부터 갈 수 있는 곳들을 전부 탐색, 갈 수 있다면 해당 위치를 방문 처리한 뒤 queue에 넣어주는 식으로 구현 (push 함수 호출)
📌문제
📌나의 코드
from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
q = deque()
def in_range(x, y):
return 0 <= x and x < n and 0 <= y and y < m
def can_go(x, y):
if not in_range(x, y):
return False
if visited[x][y] or grid[x][y] == 0:
return False
return True
def bfs():
# 상, 하, 좌, 우
dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx, ny = x + dx, y + dy
if can_go(nx, ny):
visited[nx][ny] = 1
q.append((nx, ny))
q.append((0, 0))
visited[0][0] = 1
bfs()
# 우측 하단까지 도달했으면 탈출 가능
if visited[n - 1][m - 1]:
print(1)
else:
print(0)연습문제
🟢갈 수 있는 곳들
📌문제
📌나의 코드
from collections import deque
n, k = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
start_points = deque([tuple(map(int, input().split())) for _ in range(k)])
visited = [[False] * n for _ in range(n)]
q = deque()
ans = 0
def in_range(x, y):
return 0 <= x and x < n and 0 <= y and y < n
def can_go(x, y):
return in_range(x, y) and grid[x][y] == 0 and not visited[x][y]
def push(x, y):
global ans
# 이미 방문했던 곳이 아니면 ans 증가
if not visited[x][y]:
ans += 1
visited[x][y] = True
q.append((x, y))
def bfs():
# 상, 하, 좌, 우
dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx, ny = x + dx, y + dy
if can_go(nx, ny):
push(nx, ny)
# 시작점 위치 큐가 비워질 때까지 bfs 실행
while start_points:
x, y = start_points.popleft()
push(x - 1, y - 1)
bfs()
print(ans)✏️개선점
-
dfs의 경우에는 특정 위치 한 곳을 기준으로 진행하기 때문에, 각 시작점에 대해 각각 탐색을 진행해야 한다.
-
bfs의 경우에는 queue 자료구조를 이용해 현재 방문한 위치를 여러 곳 담을 수 있기 때문에, 시작점이 여러 개인 경우 초기 queue에 전부 집어넣고 시작할 수 있다.
⇒ 여러 시작점으로부터 도달 가능한 위치를 깔끔하게 구할 수 있다.
공부 기록