1. 탐색(Search)

탐색은 많은 데이터들 가운데 원하는 데이터를 찾아가는 과정이다.

2. BFS

BFS는 넓이 우선 탐색이라고 불리며 그래프에서 가장 가까운 곳부터 탐색하여 출력 혹은 연산하는 알고리즘이다. BFS를 구현하기 위해서 선입선출 방식인 '큐' 자료구조를 사용하는 것이 일반적이다. 가장 가까운 노드부터 큐에 넣어 가장 먼저 출력될 수 있도록 하여 점차 멀리 있는 노드로 차례로 탐색이 된다. 이때 이미 방문한 노드는 다시 재방문하지 않도록 설정을 해주어야 하며, 가장 가까운 노드가 2개 이상이 주어질 때에는 어떤 순서(낮은 값부터, 높은 값부터)를 지켜가며 탐색할 것인지도 설정해야 한다. 위 그림은 시작 노드인 1이 큐에 삽입된 후 출력이되어 방문할 수 있는 곳을 찾아 큐에 삽입한다. 그리고 큐에 들어온 순서대로 노드 번호가 출력되어 나오면서 출력된 노드와 연결된 노드의 번호를 큐에 삽입한다. 이런 방식으로 가장 가까운 노드부터 찾아가 그 노드를 큐에 삽입하는 형식이다.
그림은 level로 탐색할 때 가장 낮은 level로 탐색하는 것을 볼 수 있다.
그림은 값이 낮은 순서부터 탐색해 나가는 형식이다. 그래프(트리)형식은 인접 행렬이 뿐만 아니라 인접 리스트나 배열 리스트도 문제 설정이 될 수 있다. 중요한 것은 문제의 조건에 따라서 현재 조건에서 해결 할 수 있는 가장 가까운 부분부터 방문하여 진행하기 때문에 BFS를 '최단거리'찾기 알고리즘이라 부르기도 한다.
문제를 살펴보며 좀 더 자세히 알아보자. 이번 문제는 ArrayList로 설정된 형식의 문제다.

3.1 문제

용배가 사는 아파트 엘리베이터가 고장이 났다. 엘리베이터는 한 번에 밑으로 2칸, 밑으로 5칸, 위로 2칸으로 밖에 움직이지 않는다고 할 때, 용배의 집이 k층이라면 1층으로 가장 빨리 내려가기 위해 몇 번의 엘리베이터의 버튼을 눌러야 하는지 출력하시오. (아파트의 층 수 n(6< n <= 100), 용배의 집 층 수 k(1 < n <= 100))
n = 20, k = 13

3.2 풀이

위 그림과 같이 용배가 있는 현재의 층부터 갈 수 있는 모든 층을 하나씩 탐색하며 level을 순차적으로 내려간다. 한 번 방문한 층은 다시 방문하지 않도록 체크 배열을 만들고 가장 낮은 level에서 1층이 나온다면 함수를 종료하도록 한다.
그리고 거리를 측정할 리스트를 생성하여 해당 층에 몇 번 만에 도착했는지 횟수를 입력하도록 한다. (해당 층 도착 횟수 = 이전 방문 층 도착 횟수 + 1)
level 1의 값은 1번으로 갈 수 있는 모든 층을 나타내며 level 2는 두 번의 방문으로 도착할 수 있는 층을 나타낸다. 즉 level이 몇 번의 방문 횟수를 통해 1층을 도착할 수 있는지 나타내며 가장 낮은 level에서 1층을 방문할 수 있는지 출력하면 된다.

from collections import deque
def BFS(k):
    dQ = deque() # 큐 자료구조 생성
    dQ.append(k) # 현재 층 입력
    while len(dQ): # 해당 층에서 방문할 수 있는 모든 층이 끝날 때까지
        floor = dQ.popleft() # 현재 층을 시작으로 
        if floor == 1: # 층이 1층이라면 함수 종료
            return
        else:
            for i in flist:# 층이 움직이는 범위
                nextF = floor + i # 현재 층에서 엘리베이터가 움직일 수 있는 다음 층
                if 0 < nextF <= n and chArr[nextF] == 0: # 아파트 층의 범위 안에서, 그리고 한 번 방문한 층은 다시 방문하지 않도록.
                    dQ.append(nextF) # 도착한 층수 입력
                    chArr[nextF] = 1 # 도착한 층 방문 체크
                    dist[nextF] = dist[floor] + 1 # 방문한 층이 몇 번만에 도착했는지 횟수 입력
# deque를 먼저 import 한 후
if __name__ == '__main__':
    n, k = map(int, input().split()) # 입력부
    chArr = [0] * (n + 1) # 한 번 방문한 층은 다시 방문하지 않도록 체크 배열 생성
    chArr[k] = 1 # 시작층 k를 1로 하여 다시 방문하지 않도록
    dist = [0] * (n + 1) # 방문한 층이 몇 번만에 도착하는지 횟수를 입력(인덱스 번호가 층 번호)
    flist = [-2, -5, 2] # 엘리베이터가 1번 움직여 도착할 수 있는 층
    BFS(k)
    print(dist[1]) # 1층은 몇 번째에 도착하였는지 횟수 출력
출력:
3
모든 층수 출력: print(dist)
층: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
[0, 3, 4, 2, 3, 3, 2, 3, 1, 2, 2, 1, 3, 0, 0, 1, 0, 2, 0, 3, 0]