🐰 BFS 개념 및 구현 🐰
가장 기본적인 그래프 탐색 알고리즘
BFS를 구현하는 기본적인 코드는 다음과 같다.
def bfs(graph, visited, v): # 탐색 시작 정점 v
queue = deque()
visited[v] = True
queue.append(v)
while len(queue)>0:
for vtx in graph[v]:
if not visited[vtx]:
queue.append(vtx)
visited[vtx] = True
- queue에서 정점 하나를 꺼낸다.
- 그 정점과 연결되어 있는 정점 중에 아직 방문하지 않은 모든 정점을 queue에 추가한다. 이때 해당 정점을 방문했음을 기록하여, 이미 방문한 정점을 다시 queue에 집어넣는 일을 방지한다.
- 위 작업을 queue가 빌 때까지 반복한다. queue가 비었다는 건 모든 연결된 정점을 방문했음을 의미한다.
🥬 백준 #1012 유기농 배추 🥬
https://www.acmicpc.net/problem/1012
solved.ac CLASS3 쭉 풀고 있는데 거기에 DFS/BFS 문제가 많아서 몇 개 풀어봤당. 그랬더니 어느정도 공통점이 보인다.
정말 단순하게 생각해서, 아래 두 가지 작업을 문제에 맞는 방식으로 해주면 된다.
- 연결된 정점을 큐에 집어넣기
- 방문했다는 걸 어떤 식으로든 기록하기(꼭 visited 리스트를 선언할 필요가 없다.)
보통 실제 문제에서는 이 유기농 배추 문제처럼 보드판을 주고, "상하좌우로 이동 가능하다"라는 조건 하에서 DFS/BFS를 활용하는 식으로 출제되는 것 같다. 기본 BFS 코드에서는 정점 번호를 큐에 집어넣지만, 보드판이기 때문에 튜플 형식으로 (행,열) 값을 큐에 집어넣는다. 그 다음 정점을 하나씩 꺼내서 그 정점의 상,하,좌,우를 탐색하면 된다. 이 단계에서 문제마다 적절한 작업을 해주면 됨.
참고로 상하좌우로 이동이 가능하다"라는 건 결국 (x,y) 정점이 (x-1,y) (x+1,y) (x,y-1) (x,y+1) 이렇게 네 정점과 연결되어 있다는 걸 의미한다.
1012번 문제의 경우 아래와 같은 그래프에서 이 그래프가 몇 개의 연결 요소로 이뤄져 있는지를 구하는 문제와 같당. #11724 연결 요소의 개수 ➡️ 이 문제와 사실상 같음.
그래서 네 방향 탐색 시 별도로 해줄 작업은 없고, queue가 비었다는 건 그 정점과 연결된 모든 정점을 방문했다는 뜻 즉 연결 요소의 모든 정점을 방문했다는 뜻이므로 cnt를 1 증가시키면 된다.
방문 여부를 기록하는 부분이 좀 재밌었는데, 어차피 특정 좌표에 배추가 존재하는지만 확인하면 그 좌표에 있는 정보는 다시 쓸 일이 없기 때문에 배추 존재 확인 후 그 좌표의 값을 0으로 바꿔버림으로써 방문 여부를 기록했다. 2차원 행렬을 사용해서 방문 여부를 기록하는 경우는 거의 없는 듯하다. ㅇㅅㅇ!
아래는 소스코드
from collections import deque as dq
import sys
t = int(sys.stdin.readline())
def sol():
m, n, k = map(int, sys.stdin.readline().split())
graph = [[0]*(n+1) for _ in range(m+1)]
list = dq()
for _ in range(k):
x, y = map(int, sys.stdin.readline().split())
graph[x][y] = 1
list.append((x,y))
queue = dq()
cnt = 0
for i in range(k):
vtx = list[i]
x = vtx[0]
y = vtx[1]
if graph[x][y]==1:
queue.append(vtx)
cnt+=1
while len(queue)>0:
vtx = queue.popleft()
x = vtx[0]
y = vtx[1]
if graph[x][y+1] == 1:
queue.append((x,y+1))
graph[x][y+1]=0
if graph[x][y-1] == 1:
queue.append((x,y-1))
graph[x][y-1]=0
if graph[x-1][y] == 1:
queue.append((x-1,y))
graph[x-1][y]=0
if graph[x+1][y] == 1:
queue.append((x+1,y))
graph[x+1][y]=0
# visited 리스트를 따로 만들지 않고 방문했을 경우 1을 0으로 바꿔줌
print(cnt)
for i in range(t):
sol()🍅 백준 #7576 토마토 🍅
문제가 다들 친환경적이고 귀엽군
https://www.acmicpc.net/problem/7576
요 문제도 아주 재밌었당. CLASS3에 있어서 도전하다가 때려쳤는데 선종오빠가 준 문제 리스트에 있어서 재도전 했삼.
기본적인 구현은 유기농 배추 문제와 별 다를 게 없었다. '상하좌우의 토마토를 익게 한다'는 조건 == '상하좌우로 이동 가능하다'이기 때문에. 요 문제의 관건은 며칠이 지났는지를 대체 어떻게 기록할 것인가! 였음. (큐에 탐색 처음부터 끝까지 모든 정점을 와다다 넣는 게 아니라 날짜 사이의 브레이크 포인트가 필요했다.)
결론적으로는 두 개의 큐(queue)를 사용함으로써 해결할 수 있었당. fq, sq 두 개의 큐를 두고 이 둘을 번갈아가며 사용했다.
q1: n일째에 익은 상태인 토마토들이 들어있음
q2: q1의 모든 정점들에 대한 BFS 결과가 들어있음. 즉 q1의 정점들과 연결된 모든 정점들이 들어있다. 토마토🍅로 이야기하자면 q1에 들어있는 토마토들에 의해 n일차에 새롭게 익게된 토마토덜,,,
q1이 비면 하루가 지났다고 생각해 cnt 를 증가시켰다. 그 다음 q1,q2를 맞바꿔 다시 BFS했다. BFS 시작 시에 q2는 항상 빈 큐이게끔. BFS가 끝났는데 두 큐가 모두 비어있다는 건 더이상 익을 수 있는 토마토가 없다는 뜻이므로 while문을 종료한다.
유의해야 했던 건, 모든 토마토가 익었음에도 불구하고 큐에 정점이 남아있을 수 있다는 점이다. 따라서 updated라는 변수를 두고 해당 BFS에서 새롭게 익은 토마토가 있는지를 검사했당. 새롭게 익은 토마토가 있을 경우에만 cnt를 증가시켰다.
모든 BFS가 끝난 다음 2중 for문으로 그래프를 순회했을 때 0이 존재하는 경우 cnt값을 -1로 만들어줬다.
아래는 소스코드
import sys
from collections import deque as dq
m,n = [int(i) for i in sys.stdin.readline().split()] # n:행, m:열
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
fq = dq()
sq = dq()
cnt = 0
for i in range(n):
for j in range(m):
if graph[i][j]==1:
fq.append((i,j))
def bfs(q1,q2):
global cnt
updated = 0
while len(q1)>0:
nx,ny = q1.popleft()
if nx-1>=0 and graph[nx-1][ny]==0: # 상
graph[nx-1][ny]=1
q2.append((nx-1,ny))
updated = 1
if nx+1<n and graph[nx+1][ny]==0: # 하
graph[nx+1][ny]=1
q2.append((nx+1,ny))
updated = 1
if ny-1>=0 and graph[nx][ny-1]==0: # 좌
graph[nx][ny-1]=1
q2.append((nx,ny-1))
updated = 1
if ny+1<m and graph[nx][ny+1]==0: # 우
graph[nx][ny+1]=1
q2.append((nx,ny+1))
updated = 1
if updated:
cnt+=1
while len(fq)>0 or len(sq)>0:
if cnt%2==0:
bfs(fq,sq)
else:
bfs(sq,fq)
for i in range(n):
for j in range(m):
if graph[i][j]==0:
cnt = -1
break
if cnt == -1:
break
print(cnt)+) #5427 불 문제까지 풀어보다가 내가 되게 신기하게 풀었다는 걸 깨달음... WOW
큐 두 개로 나눠서 날짜를 기록할 게 아니라 그냥 BFS로 모든 가능한 노드를 방문하고 노드에 적혀있는 값 중에 최댓값을 리턴하면 된다. BFS를 끝내고 나면 노드에는 해당 노드가 익기까지 걸린 날짜가 기록되어 있게되므로. 헐랭~~ 다른 것도 다시 풀어야지
방법 생각해내다가 했던 낙서로 마무링
벽부수기랑 불피하기 문제는 BFS로 하는 경로탐색 문제 같던데 그건 또 새로운 유형 같아서 재밌을듯. 코테 문제 푸는 거 재밌는데 이걸 나중에 시간 내에 푸는 게 가능할까?가 의문이다. 흐음
+)
실버 달성 추카추카욤^_^ 브론즈 탈출 얏호
