BFS(Breadth First Search) 너비 우선 탐색
- 가중치가 없는 그래프에서 시작점에서 끝점까지의 최단 경로를 찾을 수 있다.
- 가중치가 있는 그래프에서는 '다익스트라' 알고리즘 사용
- 주로 Queue를 이용해서 구현한다.
- 노드의 개수 N, 시간복잡도 O(N)
구현 과정
- 탐색을 시작하는 칸을 큐에 넣고 방문 처리
- 큐에서 pop해서 방문하지 않은 노드의 상하좌우로 인접한 노드 정보를 모두 큐에 넣고 현재 노드(pop한 노드) 방문처리 한다.
- 큐가 빌때까지 반복
BFS 문제 - 1926번 그림
https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로
www.acmicpc.net
from collections import deque
n, m = map(int, input().split()) # 세로, 가로
board = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
answer = [] # 넓이를 저장할 리스트
# 그림의 개수, 가장 큰 넓이 출력
# 그림 = 1로 연결된 것,
def bfs(x, y): # 탐색 위치, 넓이
# 그림이 시작 하는 위치에서 큐 시작
board[x][y] = 0 # 현재 위치 방문 체크
queue = deque() # 큐 생성
queue.append([x, y]) # 큐에 해당 칸 넣기
cnt = 1 # 그림 칸 개수
while queue: # 큐가 빌때까지
a, b = queue.popleft() # 현재 탐색 위치 제거(탐색 완료)
for d in range(4): # 상하좌우 확인
nx = a + dx[d]
ny = b + dy[d]
# 2차원 배열에서 벗어나지 않고, 다음 위치가 1(그림이 있는)인 경우
if -1 < nx < n and -1 < ny < m and board[nx][ny] == 1:
board[nx][ny] = 0 # 다음 위치 방문 체크
queue.append([nx, ny]) # 큐에 탐색할 위치 넣기
cnt += 1 # 그림 칸 개수
return cnt
# 그림의 시작점 찾기
for i in range(n):
for j in range(m):
if board[i][j] == 1: # 그림이 있는 위치
answer.append(bfs(i, j))
if len(answer) == 0: # 그림이 하나도 없는 경우
print(len(answer))
print(0)
else:
print(len(answer))
print(max(answer))
BFS 문제 -2667번 단지번호붙이기
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
from collections import deque
n = int(input())
board = [list(map(int, input())) for _ in range(n)]
answer = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 1 집이 있는곳, 0 집이 없는 곳
# 단지 개수, 단지에 속하는 집 개수 출력
def bfs(x, y):
queue = deque()
queue.append([x, y])
board[x][y] = 0 # 방문체크
cnt = 1
while queue:
px, py = queue.popleft()
for d in range(4):
nx = px + dx[d]
ny = py + dy[d]
# 방문 가능한 곳인지 확인
if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
board[nx][ny] = 0 # 다음 방문 체크
queue.append([nx, ny]) # 큐 입력
cnt += 1
return cnt # 집 개수 출력
for i in range(n):
for j in range(n):
if board[i][j] == 1:
answer.append(bfs(i, j))
answer.sort()
print(len(answer))
for x in answer:
print(x)
BFS 문제 - 2178번 미로 탐색
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
from collections import deque
n, m = map(int, input().split()) # 가로, 세로
board = [list(map(int, input())) for _ in range(n)]
# 1: 이동할 수 있는 칸, 0: 이동 불가능
# (1,1)에서 출발 (N,M) 위치로 이동할 때 지나야 하는 최소 칸 수 출력
def bfs(x, y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque() # 큐 생성
queue.append([x, y]) # 시작점 체크
while queue:
a, b = queue.popleft()
for d in range(4):
nx = a + dx[d]
ny = b + dy[d]
# 방문 가능한 곳
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
queue.append([nx, ny]) # 큐 삽입
board[nx][ny] = board[a][b] + 1
return board[n - 1][m - 1]
print(bfs(0,0))
BFS 문제 - 7576번 토마토
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
from collections import deque
m, n = map(int, input().split()) # 가로, 세로
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
day = 0
# 토마토는 하루가 지날 때 마다 안익은 토마토는 인접한 익은 토마토의 영향을 받아 익게 된다.
# 모든 토마토가 익게 되는 일수 출력, 모두 익지 못하는 상황에는 -1 출력
# 익은 토마토 1, 안익은 토마토 0, 토마토가 없는 경우 -1
# 시작 위치 큐에 넣기
for i in range(n):
for j in range(m):
if board[i][j] == 1:
queue.append([i, j])
def bfs():
while queue:
px, py = queue.popleft()
for d in range(4):
nx = px + dx[d]
ny = py + dy[d]
# 토마토가 익지 않았을 경우
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
board[nx][ny] = board[px][py] + 1
queue.append([nx, ny])
bfs()
# 익지 않은 토마토가 있으면 -1 출력, 모두 다 익은 경우 가장 큰 날짜를 찾아서 출력
for i in range(n):
for j in range(m):
if board[i][j] == 0:
print(-1)
exit(0)
maxValue = max(board[i])
day = max(maxValue, day)
# 처음 시작을 1로 했기 때문에 -1
print(day-1)
https://www.acmicpc.net/problem/4179
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문
www.acmicpc.net
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
from collections import deque
#n, k = 5, 17 # 수빈이가 있는 위치, 동생이 있는 위치
n, k = map(int, input().split())
MAX = 10 ** 5
visited = [0]*(MAX+1)
# 걷기 : 1초 후 x-1, x+1로이동
# 순간이동 : 1초 후 2*x 으로 이동
# 가장 빠른 시간 찾기
def bfs():
queue = deque()
queue.append(n)
while queue:
x = queue.popleft()
if x == k:
print(visited[x])
break
for nx in (x-1, x+1, x*2):
if 0 <= nx <= MAX and not visited[nx]:
visited[nx] = visited[x] + 1
queue.append(nx)
bfs()
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
'CS > 자료구조&알고리즘' 카테고리의 다른 글
| [알고리즘] 위상 정렬(Topological Sort) - 줄 세우기, 선수 과목 (3) | 2022.09.19 |
|---|---|
| [알고리즘] 깊이 우선 탐색 DFS(Depth First Search) (0) | 2022.09.18 |
| [알고리즘] 동적 계획법(Dynamic Programming) (0) | 2022.09.17 |
| [알고리즘] 자료구조 - 스택, 큐, 덱, 힙, 우선순위 큐 (0) | 2022.09.16 |
| [알고리즘] 해시(Hash), 파이썬 딕셔너리(Dictionary) (0) | 2022.09.15 |
