알고리즘 문제풀이:: 프로그래머스 BFS 송아지 찾기

오랜만에 BFS문제 푸니까 벌써 버벅거린다.

그리고 C++로 풀었던 문제라서 그런지 파이썬으로 풀기 많이 어색했다.

프로그래머스 풀이

문제리뷰

송아지 찾기

횟수를 구하는 BFS 문제라서 강의 안 듣고 풀었는데 두 가지 문제 때문에 만점이 안 나와서 애먹었다.

1. s > e일 때 리스트 크기 문제

• e가 작으면 s 방문할 때 크기가 안 맞아서 안 돌아간다.
• 그래서 end = max(s, e)를 통해 end 범위를 늘리는 방식으로 고쳤다.

2. q.pop() 문제

• queue 방식으로 사용해야 했는데 stack 방식으로 이용해서 안 됐던거 같다.

---

Python

송아지 찾기

from collections import deque
dx = [1, -1, 5]

def solution(s, e):
    answer = 10001
    
    end = max(s, e)
    ch = [-1]*len(range(0, end+6))
    q = deque([s])
    ch[s] = 0
    while len(q) > 0:
        cur = q.popleft()
        if cur == e: 
            answer = ch[e]
            break
                
        for x in dx:
            nx = cur+x
            if nx >= end+6 or nx < 0: continue
            if ch[nx] >= 0: continue
            
            ch[nx] = ch[cur] + 1
            q.append(nx)
    #print(ch)
    return answer