글 읽기 - 간단한 bfs로 풀이를 하려는데 틀립니다.

omsluck 1년 전 0

예제는 다 맞고 어떤 케이스에서 틀리는 건지 잘 모르겠습니다.

방문 처리는 굳이 필요하지 않다고 생각해서 넣지 않았습니다.

9번째 줄이 잘못된 걸까요?

어떤 이유로 틀린 건지 지적해주시면 대단히 감사하겠습니다.

from collections import deque
a,b = map(int,input().split())

def bfs():
    while q:
        num, cnt = q.popleft()
        
        # 큐에 저장된 연속한 2개의 값이 b보다 크면 -> 어떤 짓을 해도 이상 b로 만들 수 없으니 return 
        if num > b and q[0][0] > b:
            return -1
        
        # b로 변환이 되는 순간 바로 return
        if num*2 == b or int(str(num)+'1') == b:
            return cnt+1

        q.append([num*2, cnt+1])
        q.append([int(str(num)+'1'), cnt+1])

q = deque()
q.append([a,1])
print(bfs())

djm03178 1년 전 1

큐에 저장된 연속한 2개의 값이 b보다 크더라도 그보다 더 뒤에 있는 값이 b보다 크지 않을 수 있습니다.

omsluck 1년 전 0

맞네요.. 제가 생각이 짧았네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

간단한 bfs로 풀이를 하려는데 틀립니다.

omsluck 1년 전 0

djm03178 1년 전 1

omsluck 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말