Algorithm - 송아지 찾기(BFS : Breadth First Search)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[송아지 찾기(BFS)]

 

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

 

현수는 스카이 콩콩을 타고 이동하는데, 한 번의 점프로 앞으로 1칸 or 뒤로 1칸 or 앞으로 5칸을 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지를 구하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다.

직선의 좌표점은 1부터 10,000까지이다.

 

*출력 설명

점프의 최소 횟수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque
sys.stdin = open('AA/input_62.txt', 'rt')

MAX = 10000
ch = [0] * (MAX + 1)
dis = [0] * (MAX + 1)
n, m = map(int, input().split())
ch[n] = 1
dis[n] = 0

dQ = deque()
dQ.append(n)

while dQ:
    now = dQ.popleft()
    if now == m:
        break
    for next in (now-1, now+1, now+5):
        if 0 < next <= MAX:
            if ch[next] == 0:
                dQ.append(next)
                ch[next] = 1
                dis[next] = dis[now] + 1
print(dis[m])

# 출력 : 3

 

input_62.txt(입력)

5 14

 

 

중요내용

1. BFS는 넓이우선탐색으로 상태트리의 레벨 순서대로 노드를 탐색한다.
2. 즉, 루트노드에서 시작해서 1레벨의 노드를 모두 탐색한 후에 2레벨의 모든 노드를 탐색하고 3레벨의 노드를 탐색하는 방법을 사용한다.
3. 또한, BFS는 큐 자료구조를 활용하여 탐색을 한다. (변수 dQ는 큐 자료구조)
4. 변수 dQ는 큐 자료구조이다.
5. 변수 MAX는 좌표의 최대 값을 의미한다.
6. 리스트 ch는 이미 방문한 위치를 재방문하지 않기 위해 사용된다. (최소 점프횟수를 구하기 때문에 재방문을 고려할 필요X)
7. 즉, 리스트 ch의 벨류 값이 0이면 사전에 방문한적이 없는 위치를 의미하고, 1이면 이미 방문한 위치임을 의미한다.
8. 리스트 dis는 이동할 수 있는 위치를 나타내는 거리 수직선으로 사용되며, 해당 리스트의 인덱스 번호는 이동한 위치를 나타낸다.
9. 리스트 dis의 벨류 값은 최초 위치로부터 점프를 시도한 횟수를 의미한다.
10. " for next in (now-1, now+1, now+5): " 코드는 next에 now-1, now+1, now+5 값들이 하나씩 들어가서 총 3번의 반복문이 실행됨을 의미한다.
11. 즉, now-1, now+1, now+5는 특정 노드에서 뻗어나오는 간선을 의미한다. (간선의 개수 = 점프로 이동할 수 있는 방법의 수)