백준 12851 파이썬

문제

숨바꼭질2

백준 12851

풀이

bfs를 이용해야하는 문제다.
조건은 다음과 같다

1. x+1 로 이동
2. x-1 로 이동
3. 2*x 로 이동

결과적으로 최적의 답 일 때 같은 경우의 수가 몇개나 존재하는 지 찾는 것

틀린 풀이 1 (시간초과)

시간 초과가 난 코드이다. 연관된 문제 백준 1697 숨바꼭질 의 문제풀이에서도 비슷하게 틀린 기억이 있다.ㅠㅠㅠ

그 원인은 이미 x라는 지점에 최선의 방법으로 방문했을 경우에 대한 처리를 해주지 않았기 때문이다.

방문처리를 해주어야 queue에 새로운 값이 들어가지 않게 되고 결국에는
시간초과를 방지할 수 있다.

   # 숨바꼭질 2 
import sys
from collections import deque
input=sys.stdin.readline



N,K=map(int,input().split())


# 경우 3가지 
# 1. x-1 
# 2. x+1
# 3. 2x 

q=deque()
q.appendleft([N,0])# start , cnt 
min_way_cnt=0# 시간 별 몇가지 경우가 나오는 지 
min_way=0


while len(q)!=0:
    start,cnt=q.popleft()
    
    if min_way!=0 and min_way<cnt:
        break
    if start==K:
        min_way=cnt
        min_way_cnt+=1
        visited[K]=0
    else:
        # 답이 아닌 경우 
        if start-1>=0 :
            q.append([start-1,cnt+1])
        if start+1<=100000 :
            q.append([start+1,cnt+1])
        if start*2<=100000 :
            q.append([start*2,cnt+1])

print(min_way)
print(min_way_cnt)

정답 코드

1. 중복 방문의 경우 하지 않도록 처리
2. 최선의 경우일 때 그 지점에 대한 방문 처리는 초기화

# 숨바꼭질 2 
import sys
from collections import deque
input=sys.stdin.readline



N,K=map(int,input().split())


q=deque()
q.appendleft([N,0])# start , cnt 
min_way_cnt=0# 시간 별 몇가지 경우가 나오는 지 
min_way=0

visited=[0 for _ in range(100001)] # 새로도입
# 이미 방문되었다면 이후에 다른 값을 계산할 필요가 없음 
while len(q)!=0:
    start,cnt=q.popleft()
    visited[start]=1
    if min_way!=0 and min_way<cnt:
        break
    if start==K:
        min_way=cnt
        min_way_cnt+=1
        visited[K]=0
    else:
        # 답이 아닌 경우 
        if start-1>=0 and visited[start-1]==0:
            q.append([start-1,cnt+1])
        if start+1<=100000 and visited[start+1]==0:
            q.append([start+1,cnt+1])
        if start*2<=100000 and visited[start*2]==0:
            q.append([start*2,cnt+1])

print(min_way)
print(min_way_cnt)

결과 정답