코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
BFS - 최소 점프
앞서 공부한 BFS(너비 우선 탐색)을 사용해 최소 점프 문제를 풀어보겠다.
문제
현수는 놀이터에서 놀다가 집으로 가려고 합니다. 놀이터의 위치와 집의 위치가 수직선상의 좌표 점으로 주어집니다. 놀이터는 수직선상의 0지점입니다.
현수는 놀이터에서 스카이콩콩을 타고 점프를 하면서 집으로 이동하려고 합니다.
점프는 다음과 같은 규칙으로 합니다.
- 현재 지점에서 앞으로 +1 만큼 점프이동할 수 있습니다.
- 현재 지점에서 뒤쪽으로 -1 만큼 점프이동할 수 있습니다.
- 현재 지점에서 앞쪽으로 +5 만큼 긴 점프이동을할 수 있습니다.
매개변수 home에 현수의 집의 위치가 주어지면 놀이터에서 집까지 최소 몇 번의 점프로 집에 도착할 수 있는지 최소 점프횟수를 구하여 반환하세요.
입출력 예
| home | answer |
|---|---|
| 10 | 2 |
| 14 | 4 |
| 25 | 5 |
| 24 | 6 |
| 345 | 69 |
제한사항
- 수직선의 좌표는 0부터 10,000까지입니다.
- 현수가 집으로 반드시 갈 수 있습니다.
코드
from collections import deque, defaultdict
def BFS(home):
# 이미 들어가 있는 원소 확인용
check = defaultdict(int)
# 처음 원소 넣기
Q = deque()
Q.append(0)
check[0] = 1
L = 0
while Q:
# 현재 레벨의 원소 개수
n = len(Q)
# 현재 레벨의 원소들 하나씩
for _ in range(n):
# 꺼내서 v에 넣음
v = Q.popleft()
# -1, +1, +5로 자식노드 만들기
for nv in [v-1, v+1, v+5]:
# 그 자식 노드가 원하는 숫자(home)이면 return L+1
if nv == home:
return L+1
# 좌표의 범위에 벗어나지 않으면서, 현재 없는 원소인 경우에만
if nv >= 0 and nv <= 10000 and check[nv] == 0:
# 다음 레벨 계산을 위해 Q에 넣기
Q.append(nv)
# 넣었다고 표시
check[nv] = 1
L += 1
def solution(home):
answer = BFS(home)
return answer
print(solution(10))
print(solution(14))
print(solution(25))
print(solution(24))
print(solution(345))
풀이
이 문제는 단순히 BFS로 계속 탐색하다가 home과 값이 동일한 노드를 만난다면 해당 노드의 레벨을 return해줘도 된다.
하지만 그렇게 동작하게 된다면, 숫자가 기하급수적으로 커졌을 시 중복된 숫자를 많이 만나게 되어 시간이 많이 걸린다.
따라서 이미 탐색했지만 home이 아닌 숫자는 다시 탐색하지 않게 표시를 해둬야 한다.
위 코드에서는 좌표의 범위만큼 0으로 채워진 check 리스트를 만들어 이 숫자를 한 번 만났을 때 표시를 해둬 중복으로 탐색을 안 하게 작성했다.
- 이미 탐색한 원소를 표시해둘
check리스트에 좌표 범위의 크기만큼0으로 채움 - 초기 좌표
0을Q에 삽입 후표시한 후,루트(L = 0)부터 시작 - 현재 레벨(L)의 원소 개수를 구해
n에 저장 - 현재 레벨의 원소 중 첫 번째 원소부터 꺼내
v에 저장 - 이동 조건인
-1,+1,+5를 한 자식 노드들 생성 - 이 자식 노드가 home과 동일하다면 자식 노드의 레벨
(L+1)을return - 동일하지 않다면 좌표의 범위에서 벗어나지 않고, 한 번도 탐색하지 않은 숫자만
Q에 삽입 및 표시 - 해당 레벨의 원소의 자식노드 중
home과 동일한 노드가 없다면 그 자식 노드를 기준으로 다시 탐색 ->L + 1
끄적끄적