🎈 BFS : 너비우선탐색
⚽ 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
🎈 큐 자료구조를 이용하며 동작 과정에 대해 알아보자.
- 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
(최단거리 구하는 문제에서 자주 사용된다.) → 이 유형으로 자주 사용 돼!!!
😀 BFS는 레벨탐색
✈️ 즉 간선 한 단계로 갈 수 있는 노드들을 담는거야 (방문처리)
⚽ BFS는 해당 시점(현재 노드)에서 인접한 노드를 한번에 전부 큐에 넣는다는 것이 특징이다.
- 특히 BFS 알고리즘은 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로도 효과적으로 사용된다.
⚽ 파이썬에서 BFS코드는 큐를 위해 deque 라이브러리 선언 !!
- (DFS때와 마찬가지로 0번 인덱스는 사용하지 않는다.)
- 문제를 풀면서 익혀보자.
✈️ BFS 문제풀 때 마인드
🧨 송아지 찾기(BFS : 상태트리탐색)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.
▣ 출력설명
점프의 최소횟수를 구한다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
import sys
# sys.stdin = open("input.text", "rt")
from collections import deque
s,e = map(int, input().split())
#최대 좌표수만큼 만들어주면 돼.
MAX = 10001
dis = [0] * MAX
ch = [0] * MAX
ch[s] = 1 #현재 위치는 방문 표시 후 시작.
#출발점은 s인데 어차피 시작거리는 0
dq = deque()
dq.append(s) #현재 위치 추가해주고 시작하는거야!
dx = [-1,1,5] #방향 총 3가지 +1, -1, +5
while dq:
now = dq.popleft() #현재위치 꺼내서
if now == e: #목표지점에 도착하면 끝이지.
break
for i in range(3):
nx = now + dx[i]
if 0<=nx<MAX: # 좌표 범위 내에 있으면서
if ch[nx] == 0: #방문 전이라면.
dq.append(nx)
ch[nx] = 1
dis[nx] = dis[now] + 1 #위치 갱신까지.
print(dis[e]) #목표지점에 도착하면해당 문제 : 일차원 상의 최단 거리 !
문제를 보면 현수와 송아지의 위치가 주어진다. 송아지 위치까지 갈 때 점프의 최소 횟수를 구하는 것인데, 이런 유형이 바로 "최단거리" 문제이다!
BFS 역시 상태트리로 시각화하면서 푸는건 같아 !
대신 점프의 최소 횟수를 구하는 것이라서 거리를 나타내는 리스트가 항상 따라 붙을꺼야!
-
dis라는 거리 리스트를 만들고 출발해서 몇번만에 갈 수 있는지를 생각하자
이동할 때 3가지 방법이 존재하므로 현재 위치에서 갈 수 있는 방향 3가지 → 현재 위치마다 3가지씩 뻗어나간다고 생각해야겠다. 그리고 이 3가지 모두 한번에 갈 수 있는 인접노드! 이걸 큐에 모두 넣는거야. -
BFS는 인접노드들을 모두 큐에 넣는다.
그리고 최단거리이므로 현재 위치에서 한번에 갈 수 있는곳이 (현재까지의 거리 + 1)로 표현해 !!
- BFS 문제도 DFS처럼 방문한 곳 다시 방문 안하도록 중복 체크 리스트 필요해 !
그리고 원하는 위치가 나오면 거기서 끝이야. 최초로 나오면 그게 최소거리이기 때문 !!!
- 이런 유형이 나오면 바로 BFS로 풀 수 있겠구나 생각들 정도로 문제 풀어나가자.
✈️ BFS에서 생각할 것
- 현재 위치에서 뻗어 나가는 가지 수
- 최단거리 → BFS문제 겠구나. 거리 리스트와 중복 체크 리스트 필요하지 않을까?
- 시작지점 방문처리(체크)하고 들어가
- 데크가 빌 때까지 계속 반복하면서 현재위치를 꺼내. 그리고 현재위치에서 뻗어 나가야 하는 가지 수 만큼 확인하자
⚽ BFS 역시 DFS처럼 방향벡터 활용하는게 좋아
- 현재 좌표 설정값 내에 있으면서 방문 전이라면 ! 이제 큐에 넣어주는거지 + 현재 위치 + 1을 dis (거리 리스트) 넣어주기
최단거리 구할때
⚽ 위치 갱신하는거 잊지말자
dis[nx] = dis[now] + 1
ch[nx] = 1 현재 위치 + 1 해줘서 최단거리 갱신해주는거야 !
그리고 현재 위치는 방문 표시 (다시 방문하지 않도록)
목표지점(e)에 도착하면 탈출하면 돼 !
⚽ 또 다른 문제를 보면서 확인해보자
미로의 최단거리 통로(BFS 활용)
7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
위와 같은 경로가 최단 경로이며 경로수는 12이다.
▣ 입력설명
7*7 격자판의 정보가 주어집니다.
▣ 출력설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.
▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
▣ 출력예제 1
12
import sys
# sys.stdin = open("input.text", "rt")
from collections import deque
g = [list(map(int, input().split())) for _ in range(7)]
#0으로만 이동해야함.
dq = deque()
dis = [[0] * 7 for _ in range(7)]
dq.append((0,0)) #시작위치 삽입하고 시작
g[0][0] = 1 #시작점 방문 표시 후 시작
dx = [1,-1,0,0]
dy = [0,0,1,-1]
while dq:
x,y = dq.popleft()
for i in range(4): #현재 위치에서 4가지 방향 모두 확인 !!
nx = x + dx[i]
ny = y +dy[i]
if 0<=nx<7 and 0<=ny<7:
if g[nx][ny] == 0: #아직 방문 전.
dq.append((nx,ny)) #큐에 삽입
g[nx][ny] = 1 #방문 표시 후 벽으로 만드는게 방문표시하는 것과 동일
dis[nx][ny] = dis[x][y] + 1 #현재 위치 + 1
if g[6][6] == 0:
print(-1)
else:
print(dis[6][6])
⚽ BFS로 풀어보기 : 이차원 상의 최단거리
이 문제를 보면 처음에 그래프가 주어져 이런 문제는 보자마자 BFS 생각할 수 있다. 문제에서 애초에 최단거리를 구하라고 얘기해주잖아.
거기에 이렇게 그래프에 0,1로 표시할 수 있다면 따로 중복체크 리스트가 필요하진 않아. 그래프에 표시하면 돼!
최단거리를 나타낼 리스트만 있으면 되는데 똑같이 2차원 리스트를 만든 후에 현재 거리 + 1을 계속 더해나가면 쉽게 해결할 수 있다 !!
- 큐가 비면 BFS가 끝나는거야 (더이상 방문할 곳이 없기 때문!)
- 그래프 최단거리 문제 유형은 BFS로 !
🧨 BFS 응용 : 최단거리 문제
🚗 토마토(BFS 활용)
현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
▣ 입력설명
첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000 이다.
둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
▣ 출력설명
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
▣ 입력예제 1
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
▣ 출력예제 1
4
import sys
# sys.stdin = open("input.text", "rt")
from collections import deque
m,n = map(int, input().split()) #m 가로 n 세로
g = [list(map(int, input().split())) for _ in range(n)]
#1 익은 토마토 0 익지 않은 토마토 -1은 토마토가 들어있지 않은 칸
#최소.. 보자마자 최단거리 생각
dq = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dis = [[0] * m for _ in range(n)] #최소 거리
#먼저 익은 토마토 전체를 넣고 시작했어야 했다.
for i in range(n):
for j in range(m):
if g[i][j] == 1: #익은 토마토
dq.append((i,j)) #미리 다 넣어둠
#전체 다 넣어두고 시작했어야 했다. 이 생각할 수 있도록.. 문제 자주 풀자.
while dq:
x,y = dq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m: #경계선
if g[nx][ny] == 0: #아직 방문 전
g[nx][ny] = 1 #방문 처리
dis[nx][ny] = dis[x][y] + 1
dq.append((nx,ny))
#만약 g에 0이 있다면 안익은 토마토 존재.
flag = 0
res = 0 #최단거리 최댓값.
for i in range(n):
for j in range(m):
if dis[i][j] > res:
res = dis[i][j]
if g[i][j] == 0:
flag = 1
break
if flag == 1:
print(-1)
else:
print(res)🚗 코멘트
해당 문제를 보면 최단거리 유형이라는 것을 파악할 수 있었어야 했다. 그렇기에 BFS를 써야겠구나 까지 생각에 도달해야 한다.
그렇다면 필요한 것을 바로 떠올리면 되는데, dis 거리 리스트(최단거리)를 만드는 것은 다른 최단거리 문제 유형과 동일하다.
이 문제의 핵심은 그래프 전체를 탐색하면서 익은 토마토(1)을 큐에 전체 다 넣고 시작했어야 했다 !! → 먼저 탐색해야 하는 부분이었기 때문에 나중에 하면 결과값이 변해.
-
거기서 이제 뻗어나갔어야 했다.
-
내가 실수한 것은 그냥 익은 토마토 발견하자마자 바로 거기서 BFS를 시작해버렸다. 근데 익은 토마토 있는 곳이 가장 우선되기 때문에 가장 먼저 넣어두고 시작했어야 했다.
✈️ 간단할 줄 알았는데 먼저 시도해야 하는 토마토들을 미리 넣었어야 한다는 생각을 하지는 못했다.
어찌됐든 다 넣었다면 이제 다른 BFS문제들과 동일하게 접근하면 된다.
또한 중복 체크를 그냥 그래프 위에 해줄 수 있기에 따로 체크 리스트를 만들지 않아도 됐다.
- 마지막으로 거리를 확보할 때 그래프를 다시 탐색하면서 가장 큰 값을 가져오면 된다, 거기서 끝났다는 뜻이니깐. (물론 0이 있다면 그 그래프는 안된다는 뜻)
