[알고리즘] 백준 - 숨바꼭질(python 파이썬)
백준 - 숨바꼭질
과정
- 현재 위치에서 곱하기 연산을 했을 때 target값과 가장 가까운 경우 곱하기 선택
- 같은 값이 없을 경우 연산(+, -, *)을 했을 때 target 값과 가장 가까운 값을 선택
- target 값과 같아질 때까지 loop 반복
- 1차 풀이: BFS로 안품..ㅋ
- 가능하면 최대한 많이 곱하게 한다.
from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())
cur = n # 수빈이의 현재 위치
cnt = 0 # 움직인 시간
while cur != k:
tmp1 = cur * 2
tmp2 = cur + 1
tmp3 = cur - 1
tmp = [] # 4, 6, 10
tmp.append(tmp1)
tmp.append(tmp2)
tmp.append(tmp3)
arr = [] # target에서 뺀 값
for i in range(3):
arr.append(abs(k - tmp[i]))
arr2 = []
for j in range(3):
arr2.append(abs(k - tmp[j] * 2))
min_ = min(arr + arr2)
if min_ in arr:
# print(arr.index(min_)) # 최솟값을 저장하고 있는 인덱스 출력
cur = tmp[arr.index(min_)]
cnt += 1
else:
# print(arr2.index(min_))
cur = tmp[arr2.index(min_)]
cnt += 1
# print(cur)
print(cnt)
- 2차 풀이: BFS로 품. 최종 카운트가 이상함.
from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())
def bfs(n, k):
queue = deque()
queue.append(n)
cnt = 0
tmp = [0]
while queue:
cur = queue.popleft()
print(cur)
if cur == k:
return cnt
queue.append(cur - 1)
queue.append(cur + 1)
queue.append(cur * 2)
cnt += 1
print(bfs(n, k))
Author And Source
이 문제에 관하여([알고리즘] 백준 - 숨바꼭질(python 파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@sqaurelu/알고리즘-백준-숨바꼭질python-파이썬
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())
cur = n # 수빈이의 현재 위치
cnt = 0 # 움직인 시간
while cur != k:
tmp1 = cur * 2
tmp2 = cur + 1
tmp3 = cur - 1
tmp = [] # 4, 6, 10
tmp.append(tmp1)
tmp.append(tmp2)
tmp.append(tmp3)
arr = [] # target에서 뺀 값
for i in range(3):
arr.append(abs(k - tmp[i]))
arr2 = []
for j in range(3):
arr2.append(abs(k - tmp[j] * 2))
min_ = min(arr + arr2)
if min_ in arr:
# print(arr.index(min_)) # 최솟값을 저장하고 있는 인덱스 출력
cur = tmp[arr.index(min_)]
cnt += 1
else:
# print(arr2.index(min_))
cur = tmp[arr2.index(min_)]
cnt += 1
# print(cur)
print(cnt)
from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())
def bfs(n, k):
queue = deque()
queue.append(n)
cnt = 0
tmp = [0]
while queue:
cur = queue.popleft()
print(cur)
if cur == k:
return cnt
queue.append(cur - 1)
queue.append(cur + 1)
queue.append(cur * 2)
cnt += 1
print(bfs(n, k))
Author And Source
이 문제에 관하여([알고리즘] 백준 - 숨바꼭질(python 파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sqaurelu/알고리즘-백준-숨바꼭질python-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)