송아지 찾기 (BFS)

송아지 찾기 (BFS: Breadth First Search) 문제는 그래프 탐색 알고리즘인 **너비 우선 탐색(BFS)**을 활용하여 해결하는 대표적인 문제예요.

 

전체코드

import sys
from collections import deque
sys.stdin = open("C:/Users/csh/Documents/코딩테스트/BFS/input.txt", "r")
# 5 14 
# 송아지 찾기 (BFS)

MAX = 10000
ch = [0] * (MAX + 1) # 방문여부 확인
dis = [0] * (MAX + 1) # 송아지까지의 거리

n,m = map(int,input().split()) #   n: 현수의 위치, m: 송아지의 위치

ch[n] = 1 # 현수의 위치 방문처리
dis[n] = 0 # 현수의 위치까지의 거리는 0

dq = deque() # deque 생성
dq.append(n) # 현수의 위치를 deque에 넣기

while dq: # deque가 빌때까지 반복

    now = dq.popleft() # 현수의 위치를 deque에서 꺼내기

    if now == m: # 송아지의 위치에 도착하면 종료
        break # 송아지의 위치에 도착하면 종료

    for next in (now -1, now +1 , now +5): # 세가지 경우의 수
        if 0 < next <= MAX: # 범위안에 있을때
            if ch[next] == 0: # 방문하지 않았다면
                dq.append(next) # deque에 넣기
                ch[next] = 1 # 방문처리
                dis[next] = dis[now] + 1 # 거리계산

print(dis[m]) # 송아지까지의 거리 출력

 

📌 문제 설명

수직선 위에 현수와 송아지가 위치해 있습니다.

• 현수는 현재 점 N에 있고, 송아지는 점 M에 있어요.
• 현수는 +1, -1, ×2 세 가지 방법으로 이동할 수 있어요.
• 최소 몇 번의 이동으로 송아지에게 갈 수 있는지 구하는 문제입니다.

 

🛠 해결 방법 (BFS 활용)

BFS (너비 우선 탐색)을 사용하는 이유는 "최단 거리"를 찾는 데 최적화된 알고리즘이기 때문이에요.
DFS(깊이 우선 탐색)는 특정 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식이라 최단 거리 문제에 적합하지 않아요.

BFS에서는 큐(Queue)를 활용해서 한 단계씩 이동하면서 탐색합니다.

---

📜 구현 방법

1. 큐(Queue) 초기화
   • Queue에 현수의 시작 위치(N)를 추가합니다.
   • 동시에 방문 여부를 확인할 visited 리스트를 생성합니다.
2. BFS 탐색 시작
   • while문을 사용하여 큐가 빌 때까지 반복합니다.
   • 현재 위치에서 이동할 수 있는 3가지 경우 (+1, -1, ×2)를 확인합니다.
   • 만약 송아지 위치(M)에 도착하면 바로 종료하고 이동 횟수를 출력합니다.
   • 아직 방문하지 않은 위치는 큐에 추가하고, visited 배열에 체크합니다.
3. 최소 횟수 반환
   • BFS의 특성상 처음 M을 찾는 순간이 가장 빠른 경우이므로, 바로 결과를 반환합니다.