[알고리즘] 너비 우선 탐색 BFS(Breadth First Search) - 최단 경로

BFS(Breadth First Search) 너비 우선 탐색

• 가중치가 없는 그래프에서 시작점에서 끝점까지의 최단 경로를 찾을 수 있다.
  • 가중치가 있는 그래프에서는 '다익스트라' 알고리즘 사용
• 주로 Queue를 이용해서 구현한다.
• 노드의 개수 N, 시간복잡도 O(N)

 

구현 과정

• 탐색을 시작하는 칸을 큐에 넣고 방문 처리
• 큐에서 pop해서 방문하지 않은 노드의 상하좌우로 인접한 노드 정보를 모두 큐에 넣고 현재 노드(pop한 노드) 방문처리 한다.
• 큐가 빌때까지 반복

 

BFS 문제 - 1926번 그림

https://www.acmicpc.net/problem/1926

1926번: 그림

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번: 단지번호붙이기

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번: 미로 탐색

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번: 토마토

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번: 불!

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

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번: 연구소

 

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기