글 읽기 - [파이썬] 무엇이 다른가요? (꼭 답변 부탁드립니다 ㅠㅠ)

coding_master 1년 전 0

12번째 줄 코드에 [v*2,v+1,v-1]라고 작성하면 맞고 [v*2,v-1,v+1]라고 작성하면 왜 틀린지 궁금합니다.

from collections import deque
a,b = map(int,input().split())
q = deque()
q.append(a)
visited = [0] * (100000+1)
while q:
  v = q.popleft()
  if v == b:
    print(visited[v])
    break
  else:
    for i in [v*2,v+1,v-1]:
      if 0 <= i <= 100000 and visited[i] == 0:
        if i == v*2:

          visited[i] = visited[v]
        else:
          visited[i] = visited[v]+1
        q.append(i)

zenith82114 1년 전 1

구현이 정확하다면 2*v, v-1, v+1를 무슨 순서로 하든 정답이어야 합니다.

[v*2,v-1,v+1]이든 [v*2,v+1,v-1]이든

입력 1 17을 넣으면 정답은 1인데 출력은 3입니다.

다익스트라 알고리즘에서는 현재 거리보다 더 짧은 거리를 찾았을 때만 갱신하게 되어 있는데

이 코드는 16줄과 18줄에서 visited를 무조건 갱신하기 때문에 이런 문제가 생기는 것 같습니다.

coding_master 1년 전 0

감사합니다 ^^

pjh6947 1년 전 0

https://www.acmicpc.net/board/...

[13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

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

문제

문제

출처

ICPC

[파이썬] 무엇이 다른가요? (꼭 답변 부탁드립니다 ㅠㅠ)

coding_master 1년 전 0

zenith82114 1년 전 1

coding_master 1년 전 0

pjh6947 1년 전 0

[13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말