글 읽기 - 12852번 python BFS 반례가 있을까요..?(틀렸습니다 82%)

rlarhkd295 3년 전 0

여러가지 예시들 다 넣어봤는데 시간도 빠르고 틀리게 나오질 않습니다.

그냥 기본적인 BFS라고 생각이 들어서

BFS로 하여금 deque에서 가장 먼저 pop되는 case가 최적 depth라고 생각하고 풀었는데(증명을 생각해보진 않았지만 거의 자명해 보였습니다.)

혹시 그 부분이 잘못된 것인가요? 그렇다면 반례가 무엇이 있을까요??

좋은 답변 기다리고 있겠습니다. 감사합니다!

from collections import deque

def BFS(X):
  Q = deque()
  #Q에는 (start,depth) 형식으로 넣어준다.
  Q.append((X,0))                          
  visited = [False for i in range(X+1)]
  #History에는 전의 수를 저장(예: 9->3으로  넘어갈 시에는 History[3] = 9)
  History = [-1 for i in range(X+1)]       
  #시작 값의 History에는 -2로 초기화
  History[X] = -2
  min_depth = 0
  while Q:
    u = Q.popleft()
    if u[0] == 1:
      min_depth = u[1]      #최초로 발견된 u[1]을 찾는 방법이 최소 depth
      break
    else:
      if u[0]%3 == 0 and not visited[u[0]//3]:
        Q.append((u[0]//3,u[1]+1))
        History[u[0]//3] = u[0]
        visited[u[0]//3] = True
      elif u[0]%2 == 0 and not visited[u[0]//2]:
        Q.append((u[0]//2,u[1]+1))
        History[u[0]//2] = u[0]
        visited[u[0]//2] = True
      if not visited[u[0]-1]:
        Q.append((u[0]-1,u[1]+1))
        History[u[0]-1] = u[0]
        visited[u[0]-1] = True
  #예외처리 해줄 것이 없는 이유가 나누어 떨어지는 한에서 3,2로 나누거나 -1을 하는 연산은 1보다 작은 수를 만들 수 없기 때문이라고 생각했습니다.

  #아래는 History를 역추적하여 어떻게 1로 만들어 졌는지 저장한다.
  backtracking = [1]
  i = 1
  while History[i] != -2:     #History[i] == 2 -> starting value
    backtracking.append(History[i])
    i = History[i]
  
  print(min_depth)
  print(*backtracking[::-1])
  return

N = int(input())
BFS(N)

kravi 3년 전 3

반례: 642

정해:
10
642 321 320 160 80 40 20 10 9 3 1

오답:
11
642 214 107 106 53 52 26 13 12 4 2 1

시작을 input값이 아니라 1로 해보세요

rlarhkd295 3년 전 0

아 23번째 줄 elif가 아니라 if군요...감사합니다..!

+ 시작을 1로 하라고 하시는건 Bottom-up 구현을 하라고 조언해 주시는 건가요?

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

문제

문제

출처

ICPC

12852번 python BFS 반례가 있을까요..?(틀렸습니다 82%)

rlarhkd295 3년 전 0

kravi 3년 전 3

rlarhkd295 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말