BFS Python 개념 코딩테스트 (2)

 

 

목차

 

 

서론

코딩테스트 계획 포스팅에서 BFS 강의에 해당하는 내용이다. 지난번엔 배열에 대해 다루고, 풀어보았다면 오늘은 BFS에 대해 풀어보고자 한다. 내가 참고한 강의는 C++로 되어 있기 때문에 개념을 이해하는데만 참고하고 실제로 쓰이는 코드는 파이썬 코드로 작성하였다. 기본적인 개념을 숙지하고, BFS 코드가 돌아가는 과정을 알아보도록 한다. 다음 포스팅에서는 문제로 넘어갈것임.

 

---

BFS 개념

BFS는 Breadth First Search의 약자로, 너비를 우선으로 탐색(방문)하는 알고리즘이다. 흔히 DFS와 비교가 되는데 DFS는 깊이(Depth)우선 탐색임. BFS는 이해를 돕기 위해 다양하게 묘사가 된다. 내가 본 유튜브 강의에서는 그림판에서 flood fill을 묘사로 했다. 하지만 내가 가장 와닿았던건, Best Friend Search이다. 약자도 비슷한 것이, 딱 좋은 예시가 될 것 같다. Best Friend Search가 무엇이냐하면 친한 친구 찾기이다. 돈을 빌릴때 가장 친한놈부터 순차적으로 돈 빌려줄지 여부를 찾지 않는가? 상식적으로 말이다. 그래서 가장 가까운 놈부터 너 됨? ..너 됨? 이러면서 점점 영역을 넓혀가는 것이다. 처음에는 가장 가까운 절친(초록색)에게 부탁하고, 야지먹으면 그래도 좀 친한놈인 노랑색 친구한테 부탁하고. 갈 때 까지 가면 빨간색 친구한테 돈을 꾸고 그 다음은 대부업체가 되겠지 허허.

위는 BFS가 어떻게 돌아가는 지 이해를 돕기 위한 설명이고, 보다 정확한 알고리즘을 풀어 말하면 다음과 같다. 1) 시작하는 곳을 큐에 넣고 방문했다는 표시를 남긴다. 2) 큐에서 꺼내어 인접한곳을 훑는다. 3)이미 방문했는지(전에 돈 꿔달라고 했는데 또 꿔달라고 하면 큰일나니까.) 확인하고 방문 안했으면 큐에 넣기. 4) 모든 친구를 방문할 때 까지 반복한다.

---

 

 

BFS 코드 과정 및 파이썬 구현

BFS 코드는 거의 외우다 시피 해야된다고 한다. 하지만 무작정 하나하나 외운다기보다 코드의 과정을 외운다면 외우는 범위가 확 줄어들지 않을까.

 

<while문 돌기 전> 

• visited를 선언한다.
• queue = deque() 선언.
• dx,dy 선언.
• queue에 처음 시작점 넣기 + visited에 방문 표시.

<while문 속> # while queue: 

• x,y = queue.popleft()
• x+dx, y+dy 를 nx에 넣어 4번 돌며 주변부 확인.
• 이때 범위 벗어난곳 or 이미 방문한 곳 or 그래프에서 방문할 수 없는 곳 : continue
• 모두 해당하지 않으면 방문표시하고 queue에 넣기.

 

from colletions import deque
n, m  = 7, 10 # 7행 10열 2차원 배열(문제 그래프에 따라 알아서 바꾸기)
visited = [[False]*m for _ in range(n)] # n행m열 만들기
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()
queue.append(0,0) #시작점 0,0이라고 가정
visited[0][0] = True

while queue:
    x,y = queue.popleft()
    for i in range(4):
        nx = x + nx[i]
        ny = y + ny[i]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if visited[nx][ny] or graph[nx][ny] !=1:  #gragh는 문제에 있다고 가정
            continue
        vis[nx][ny] = True
        queue.append((nx,ny))

---

끝으로

오늘은 BFS 개념과 어떻게 코드로 구현하는 지 알아보았다. 다음에는 어떻게 이걸 이용해서 문제를 풀어갈지에 대해 알아보고자 한다. 다음 포스팅에서는 BFS 관련 문제와 내 풀이 방법 , 다른 사람 풀이 방법을 참고할 예정이다.