BFS

WooHyeong·2022년 10월 4일
0

Algorithm

목록 보기
2/41

BFS

  • Breadth First Search, 너비 우선 탐색

  • 그래프에서 인접한 노드부터 탐색하는 알고리즘

  • 선입선출 방식인 큐 자료구조를 이용하는 것이 정석

  • 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 되는 알고리즘

  • BFS의 동작 과정
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

    from collections import deque
    def bfs(graph, start, visited):
    
       queue = deque([start])
       visited[start] = True
    
       while queue:
           v = queue.popleft()
           print(v,end=' ')
           for i in graph[v]:
               if visited[i] == False:
                   queue.append(i)
                   visited[i] = True
                   
    graph = [[],
            [2,3,8],
            [1,7],
            [1,4,5],
            [3,5],
            [3,4],
            [7],
            [2,6,8],
            [1,7]]
    visited = [False] * 9
    bfs(graph, 1, visited)

연습 문제

'''
DFs/BFS 실전 문제 4. 미로 탈출
N x M 크기의 미로가 있다. 괴물이 있는 곳은 0, 괴물이 없는 곳은 1로 표시되어 있다.
미로의 출구는 (N, M)의 위치에 존재한다.
동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.

Ex)
5 6
101010
111111
000001
111111
111111

result = 10
'''
from collections import deque
import sys
n, m = map(int, sys.stdin.readline().split())
maze = []
step = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(n):
    maze.append(list(map(int, input())))

queue = deque()
queue.append((0,0))

while queue: #queue 빌 때까지
    x, y = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue

        if maze[nx][ny] == 0:
            continue

        if maze[nx][ny] == 1:
            queue.append((nx, ny))
            maze[nx][ny] = maze[x][y] + 1

print(maze[n-1][m-1])
profile
화이링~!

0개의 댓글