문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17예제 출력 1
4힌트
수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.문제 정리
# 수빈 점 N(0~100000) 동생 점 K에 있음(숨바꼭질)
# 걷거나 순간이동 가능 수빈
# 걷기 - X에서 1초후 X-1 or X+1
# 순간이동 - X에서 1초 후 2*X위치 이동
# 수빈이가 동생을 찾을 수 있는 가장 빠른 시간
# 5 10 9 18 17 (5~17은 4초 걸림)매 순간 K에 인접하기 위한 최선의 선택을 해줘야 하는 조건을 생성해줘야함
곱할건지 1 더하거나 뺄건지
첫번째 풀이
N, K = map(int, input().split())
count = 0
while N != K :
if K-(2*N) < K-(N+1):
N = 2*N
count += 1
elif K-(2*N) < K-(N-1):
N = 2*N
count += 1
elif K-(N+1) < K-(N-1):
N = N+1
count += 1
elif K-(N+1) > K-(N-1):
N = N-1
count += 1
print(count)뭔가 N이 K가 될때까지 N의 값이 if문의 조건에 해당되면 거기에 걸맞게 더해주거나 빼주거나 곱해주면 가능하겠다 싶었는데,
이러한 단순한 접근 방식으로는 풀이가 불가능했다
그래서 현재 위치, 목표 위치간의 차이 비교해서 최적의 경로 보장시킬 수 있는 너비 우선 탐색BFS로 풀어봤다
from collections import deque
def bfs(N, K):
max_limit = 100000
visited = [False] * (max_limit + 1)
queue = deque([(N, 0)])
visited[N] = True
while queue:
current_position, current_time = queue.popleft()
if current_position == K:
return current_time
next_positions = [current_position - 1, current_position + 1, current_position * 2]
for next_position in next_positions:
if 0 <= next_position <= max_limit and not visited[next_position]:
visited[next_position] = True
queue.append((next_position, current_time+1))
N, K = map(int, input().split())
result = bfs(N, K)
print(result)from collections import deque
일단 삽입 제거가 간편한 deque 사용
def bfs(N, K):
max_limit = 100000
visited = [False] * (max_limit + 1)시작 위치N과 도착 위치K를 받아 BFS함수로 최단 시간 계산
엄청 많은 최대값까지 계산을 억제하기 위해 limit 10000으로 고정
visited도 N,K범위인 0~100000까지를 다 체크하기 위해 +1까지 False로 리스트 구현
queue = deque([(N, 0)])
visited[N] = True
queue엔 현재 위치와, 소요된 시간 초기값 0을 넣어줌
그리고 이 함수가 실행되었다는 의미는 해당 N위치에 방문하였다는 의미이기에 True로 변환
while queue:
current_position, current_time = queue.popleft()
그리고 실제 queue가 존재하는동안 큐ㅜ에서 가장 왼쪽 요소를
현재 위치, 현재 걸린 시간 으로 나누어서 뽑아냄
if current_position == K:
return current_time
그렇게 계속 반복하다 현재 위치가 K에 가면 그때까지 걸린시간을 return시켜서 함수 종료
next_positions = [current_position - 1, current_position + 1, current_position * 2]
움직일 위치에 대해선 총 3가지 경우의 수가 있으므로 리스트에 담아주기
(계속 반복시킬 예정)
for next_position in next_positions:
if 0 <= next_position <= max_limit and not visited[next_position]:
visited[next_position] = True
queue.append((next_position, current_time+1))
아직 방문한적 없는 위치이고, 100000과 0 사이에 있는 포지션이라면
해당 위치는 True로 바꿔주고, 해당 큐에 append로 추가한 이후, 시간 1초를 추가시킨다.
대신 어떤게 가장 합리적인 의사결정인데? 라고 생각할 수 있지만,
첫 단계에서 다 해보고,
그다음 그 첫 단계에서 두번째 단계로 전체적으로 다 실행하는 즉,
모든 경로를 동시에 탐색해주므로, 미리 판단할 수는 없음 이 코드도
대신, 모든 가능한 이동 경로에 큐를 추가해서 처리함
N, K = map(int, input().split())
result = bfs(N, K)
print(result)
입력 받아오는 방식,
함수에 N,K를 넣어서 result에 넣고 해당 결과 출력
