[알아보자] BFS 알고리즘

*본 포스팅은 프로그래머스 코딩테스트 게임 맵 최단거리 문제를 참고했습니다. 문제시 삭제하겠습니다*

 

무려 다음날이 네이버 코테.. 하지만 필자는 BFS알고리즘과 싸우는 중 .. 실제로 듣기만했지 처음 구현해봄 여러뭐로 ㄹㅈㄷ인 상황 ... BFS에대해 뭐 자세히 이해하고 말고 할 시간이 사실 없음.. 글쓰는것도 걍 반포기해서 쓰면 좀 더 이해하겠지라는 마인드..허허

일단 시작해볼까요?

 

BFS

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

음 최단경로를 찾는다라고 필자는 이해했습니다.. 그래프와 트리구조는 음 다음에 제대로 올려보도록 하겠습니다.

코딩테스트 문제로 이해를 하는 방식으로 가죠 

 

 

일단 문제는 저 빨간 1을 향해 가는것이다. 사실 처음 문제를 맞이하면 list의 나열에 헷갈릴텐데 그냥 2차원배열로 적어둔거다.(필자도 굉장히 당황) 

 

처음은 일단 list의 해석을 했다. 그림친구가 있는 좌표가 (0,0)이라면 우리는 행렬 좌표로 생각해야한다. 현재는 5x5행렬이고 총 좌표는 (0,0) ~ (4,4)까지 Goal은 4행 4열에 있다. 

 

여기서 문제 그러면 어떻게 이동을 할 것인가? 일단 BFS에서는 상, 하, 좌, 우를 모두 탐색을 먼저한다. 그리고 가능한 지점을 가고 그 후 또 탐색을 진행을한다. 그런데 어떻게 최단거리가요?는 뒤에서 다뤄보자

 

일단  방향을 진행하는 코드 

              # 상 하 좌 우           
directions = [(-1,0),(1,0),(0,-1),(0,1)]
 
for dx, dy in directions:
   nx = x + dx 
   ny = y + dy

 

상 , 하 , 좌, 우에 대한 이해하는데도 좀 걸렸다.. ㅋㅋ 코딩에 걍 재능이 없는거 같다. 

각설하고 우리는 행렬 좌표로 이해 해야하기 때문에 왼쪽으로 가려면 열을 기준으로 -1을 해야하기 때문에 y값을 1줄여준다. 

그런 방식으로 방향을 for문을통해 돌릴 수 있다. 

 

그렇다면 우리의 지금 기준을 어떻게 알까? 간단히 0,0으로 선언을 해주면 된다. 

queue = deque()
queue.append((0,0,1)) # x=0, y=0 , depth=1

뒤에 1은 얼마나 탐색을 했는지를 위해 넣어 주어야한다. 

우리는 이제 여기서 queue에서 popleft() 즉 제일 앞에있는것을 빼준 지점의 x, y값을 통해 위의 방향으로 탐색을 하면 됩니다.

 

n , m = len(maps), len(maps[0])
visited = [[False]*m for _ in range(n)]

제일 중요한 문제 어떻게 탐색할것인가? 조건이 제일 중요합니다. 이때 저희는 visted라는 2차원 배열을 만들껀데 그 이유는 갔던데를 또가면 안되니까, 그러면 무한루프가 되게 되용 그래서 방문했다고 기록할 수 있는 2차원 배열을 만듭니다.

n,m은 총 우리 좌표 여기서는 5x5이겠죠? 그리고 visted는 5x5 False로 만들어줍니다. 

 

for dx, dy in directions:
    nx = x + dx 
    ny = y + dy 

    if 0 <= nx < n and 0 <= ny < m : 
        if not visited[nx][ny] and maps[nx][ny] == 1 : 
            queue.append((nx,ny,dist+1))
            visited[nx][ny] = True

 

자 이제 조건인데요 처음 봤을때는 되게 어려웠는데 뜯어보면 별것이 아니다. 

최초의 if조건은 현재 우리가 탐색하는 방향이 우리가 가지고 있는 행열보다 크면 안된다. 그리고 0보다 작으면 안되겠죠

그 후 방문하지 않은 , 즉 False일때 True가 되고 maps라는 2차원 배열에서 1,1만 갈 수 있으니까 그지점 이 추가 조건입니다. 

그렇게 하고 가능한 지점을 queue에 넣어줍니다. 그 후 방문한자리는 True로 변경.

while queue:
    x, y, dist = queue.popleft()
    if x == n-1 and y == m-1:
        return dist

 

사실 이조건이 먼전데 왜 이후에 설명을 하냐 이게 왜 최적인가를 설명하기 위함입니다. 

일단 pop.left()로 현재 지점을 뺍니다. 저희는 4,4가 목표이기 때문에 x,y 좌표가 4가 되면 바로 종료 합니다. 이때 아까전에 넣은 dist를 출력하면 되겠죠? 

이거를 계속 반복하는데 만약에 분기점이 나옵니다.  

이 부분에서 저희는 위로도 갈 수 있고 오른쪽으로도 갈 수 있죠 

만약에 분기점에서 현재 (2,2,7)인데 다음 queue에는 (1,3,8) 과 (2,4,8) 가 저장됩니다. 

하지만 while문에 의해서 (1,3,8)에 대한 분기가 저장이되고 (2,4,8)에대한 분기가 또 저장이되겠죠 

저희의 코드는 끝내는 이 분기에서 나눠진 값들을 향해 갑니다. 이후에 (4,4)를 먼저 어떤게 찍게되겠죠? 그러면 그거 제일 빠른 탐색인겁니다. 그후 return을 하는것이고요 

 

이해가 가시나요? 저도 말로는 조금 하겠는데 다시 코드쓰면 못쓸꺼 같은데요? 후에 실제 이동을 할 수 없는 상태에 물리면 queue에 존재하는게 없어져서 return -1을 하게 됩니다. 

 

from collections import * 

def solution(maps):
    
    n , m = len(maps), len(maps[0])
    visited = [[False]*m for _ in range(n)]
    queue = deque()
    queue.append((0,0,1))
                 #   위     아래       왼쪽       오른쪽
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        x, y, dist = queue.popleft()
        if x == n-1 and y == m-1:
            return dist
        
        for dx, dy in directions:
            nx = x + dx 
            ny = y + dy 

            if 0 <= nx < n and 0 <= ny < m : 
                if not visited[nx][ny] and maps[nx][ny] == 1 : 
                    queue.append((nx,ny,dist+1))
                    visited[nx][ny] = True           
    return -1

 

이게 전체 코드인데요.. 당장 내일 네이버코테인데 BFS 기초 문제 풀고있는 필자입니다...