문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
원래는 숨바꼭질 4를 풀려고 했었는데,
도저히 잘 되지가 않아 숨바꼭질 1부터 풀어보는걸로.
이번 풀이는 과정이 좀 많다. 험난하다...
솔브까지 약 4트 정도 하고 개선 풀이까지 있다.
🤔 생각
-
프로그래머스(점프와 순간이동)에서 풀었던 문제와 매우 비슷하다.
-
홀수/짝수로 뭔가 규칙이 존재할것이다 아마. 그게 가장 빠른 풀이 같긴 한데...
-
bfs를 공부할 목적이었으니 bfs를 사용해서 풀자!
📌 1차 풀이
from collections import deque
import sys
input = sys.stdin.readline
def bfs():
q = deque()
q.append((n,0))
while q:
x,cnt = q.popleft()
if x == k: return cnt
cnt += 1
q.append((x-1, cnt))
q.append((x+1, cnt))
q.append((2*x, cnt))
n,k = map(int, input().split())
print("%d" % bfs())
오...
그렇게 무겁게 짰다고 생각하진 않았는데
생각해보니 방문 처리도 안 해줬고, 카운트는 대체 왜 큐에 같이 넣은거지..?
무의식적으로 dp처럼 처리하려 한 것 같은데 이건 그럴 필요가 없다.(어차피 같은 레벨이면 카운트도 같다)
일단 전부 고쳐주고, 메모리 문제엔 보약(?)인 비트마스킹으로 방문처리를 해봤다.
📌 2차 풀이 (비트마스킹)
import sys
input = sys.stdin.readline
print = sys.stdout.write
def bfs():
q = [n]
ans = 0
cache = 0
while q:
tmp = []
for x in q:
if x == k: return ans
if not cache & (1 << x-1): tmp.append(x-1)
if not cache & (1 << x+1): tmp.append(x+1)
if not cache & (1 << x*2): tmp.append(2*x)
q = tmp
ans += 1
n,k = map(int, input().split())
print("%d" % bfs())내가 짰지만 참신하다
뭐가 참신해.
시간 초과... 그럴만도 하다. 메모리를 크게 절약하는 대신 매번 비트 연산을 해줘야한다.
비트 연산보다는 평범한 방문 리스트 인덱스 접근이 더 빠를 것이다.
그렇다면 방문 리스트를 만들어서 어떻게 되나 확인해보자.
중복해서 체크할 일이 없으니 리스트일 필요도 없고, 집합 형태로 하자.
📌 3차 풀이 (집합)
import sys
input = sys.stdin.readline
print = sys.stdout.write
def bfs():
q = [n]
ans = 0
cache = 0
cache = set()
while q:
tmp = []
for x in q:
if x == k: return ans
if not cache & set({x-1}):
cache.add(x-1)
tmp.append(x-1)
if not cache & set({x+1}):
cache.add(x+1)
tmp.append(x+1)
if not cache & set({x*2}):
cache.add(x*2)
tmp.append(x*2)
q = tmp
ans += 1
n,k = map(int, input().split())
print("%d" % bfs())
또??
내가 뭘 고려 안 한걸까.... 하다가 퍼뜩 떠오른게
n과 k에는 명시적인 범위가 있다.
처음에는 어차피 bfs로 하니까 답을 만나자마자 함수를 탈출 시킬 것이니, 범위 제한에 의미가 없다고 생각했는데...
경우의 수에 x+1이나 x-1만 있었으면 큰 상관이 없었을 것이다.
x*2가 있으니 범위를 크게 넘어간 값이 계속 큐잉되는 일이 생긴다...
이 부분이 영향을 끼쳤을거라 생각했고, 아래 최종풀이로 솔브했다.
📌 최종 풀이
import sys
input = sys.stdin.readline
def main():
def bfs():
q = [n]
ans = 0
cache = set()
while q:
tmp = []
for x in q:
if x == k: return ans
if x-1 >= 0 and not cache & set({x-1}):
cache.add(x-1)
tmp.append(x-1)
if x+1 < 100001 and not cache & set({x+1}):
cache.add(x+1)
tmp.append(x+1)
if x*2 < 100001 and not cache & set({x*2}):
cache.add(x*2)
tmp.append(x*2)
q = tmp
ans += 1
n,k = map(int, input().split())
print(bfs())
if __name__ == "__main__":
sys.exit(main())📌 개선 풀이 (리스트화)
import sys
input = sys.stdin.readline
def main():
def bfs():
q = [n]
cache = [False]*100001
ans = 0
while q:
tmp = []
for x in q:
if x == k:
print(ans)
return
for i in (x-1, x+1, x*2):
if 0 <= i < 100001 and not cache[i]:
cache[i] = True
tmp.append(i)
q = tmp
ans += 1
n,k = map(int, input().split())
bfs()
if __name__ == "__main__":
sys.exit(main())
✔ 회고
- 범위 제한은 웬만하면 해주자. 불필요한 조건문이 될지라도 최소 범위 초과로 인한 페일 때문에 머리 부여잡을 일은 없다... (풀고 나서 개선해주면 될일이다)
