[코딩테스트] BFS 대표 유형 공부 - 게임 맵 최단 거리 및 기타 문제들

DFS가 재귀를 죠지는 거라면

BFS는 그래프 및 최단 거리에서 알짜배기로 사용되는 테크닉

https://school.programmers.co.kr/learn/courses/30/lessons/1844/solution_groups?language=python3&type=my

프로그래머스

 

이전 포스팅에도 참고했던 것처럼 유형이 비슷하다. 여기는 외우다시피 숙지를 해놓아야한다.

https://yscho.tistory.com/68

[Graph, BFS] 벽 부수고 이동하기 - 백준

 

from collections import deque

def solution(maps) : 
    (x,y) = (0,0)
    return BFS(x,y,maps)

def BFS(x,y,maps) : 
    m = len(maps[0])
    n = len(maps)

    ### 방문 횟수 저장, 이를 바탕으로 최적 경로 추정
    visited = [ [0]*m for _ in range(n)]

    move_x = [-1,1,0,0]
    move_y = [0,0,1,-1]

    queue = deque()
    queue.append([x,y])
    visited[x][y] = 1

    while queue : 
        x,y = queue.popleft()

        if x == n-1 and y == m-1 : 
            return visited[x][y]

        for i in range(4) :
            after_x = x+move_x[i]
            after_y = y+move_y[i]

            if after_x < 0 or after_y < 0 or after_x >= n or after_y >= m :
                continue

            if visited[after_x][after_y] == 0 :
                if maps[after_x][after_y] == 1 :
                    queue.append([after_x,after_y])
                    visited[after_x][after_y] = visited[x][y] + 1

            if visited[after_x][after_y] == 1 :
                if maps[after_x][after_y] == 1 :
                    queue.append([after_x,after_y])
                    visited[after_x][after_y] = visited[x][y] + 1

    return -1

 

 

아래 유형도 동일한 백준 유형

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

import sys
from collections import deque

m, n = [int(x) for x in sys.stdin.readline().split()]

graph = []

for _ in range(m) : 
    graph.append([int(x) for x in input()])

def BFS(graph,m,n) :       
    visited = [[0]*n for _ in range(m)]

    move_x = [-1,1,0,0]
    move_y = [0,0,1,-1]

    (x,y) = (0,0)
    visited[x][y] = 1

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

    while queue :
        x, y = queue.popleft()

        if x == m-1 and y == n-1 :
            return visited[x][y]

        for i in range(4) :
            after_x = x+move_x[i]
            after_y = y+move_y[i]

            if after_x < 0 or after_y < 0 or after_x >= m or after_y >= n :
                continue

            if visited[after_x][after_y] == 0 :
                if graph[after_x][after_y] == 1 :
                    visited[after_x][after_y] = visited[x][y]+1
                    queue.append([after_x,after_y])

    return -1

print(BFS(graph,m,n))