글 읽기 - [Python] 1697 BFS로 풀었는데 틀린 부분을 못찾겠어요 ㅜ

adfad1 3년 전 0

BFS로 Jupyter NoteBook에서 코드를 작성 후 게시판에 나온 다양한 반례들에 대해 시도를 해보고 값이 잘 나옴을 확인하였지만

정작 제출만 하면 틀렸다고 뜨네요...

혹시 이 풀이의 문제점이 무엇인지 알려주실 수 있을까요?

같은 위치에 있을때는 0이 출력되게끔 코드를 추가했고 n보다 k가 더 작은 상황일 때 뒤로 1칸씩 가서 count가 나오는 것도 확인했어요 ㅠ

#1697
from collections import deque
queue = deque()    # 다음 depth 요소 값을 저장할 큐
new_queue= deque() # 매 depth마다 요소를 반복해서 돌릴 큐
visited_queue = deque() # 숫자가 중복해서 탐색하지 않게끔 체크하는 큐
n, k = map(int,input().split())
for i in range(100001):
    visited_queue.append(0)
    
nx = [-1,1,2]
###############################################    
def bfs(n,k):
    queue.append(n)
    # 출력값을 count로 선언
    count=0
    
    # n과 k가 같은 위치면 바로 찾음(0 출력)
    if n==k:
        return count
    
    
    while queue:
        # 돌릴 new_queue에 queue 값을 이전하고 새로이 채울 queue는 초기화
        for i in queue:
            new_queue.append(i)
        queue.clear()
        count+=1
        
        # 한 depth에 담긴 new_queue 값을 반복해서 실행 후 queue에 실행값들을 저장
        while new_queue:           
            x = new_queue[0]
            for i in range(3):
                if i==2:
                    dx = x * nx[i]
                else:
                    dx = x + nx[i]
                    
                if dx >=0 and dx <=100000:
                    visited_queue[dx]+=1

                if dx <0 or dx >100000:
                    continue

                if dx !=k and visited_queue[dx]==1:
                    queue.append(dx)
                
                # 탐색하다 k를 만난 순간 해당 회차인 count를 출력함으로써 함수 종료
                elif dx==k:
                    return count
                
            del new_queue[0]
###############################################

bfs(n,k)

dwax1324 3년 전 1

값을 출력해주세요

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

문제

문제

출처

ICPC

[Python] 1697 BFS로 풀었는데 틀린 부분을 못찾겠어요 ㅜ

adfad1 3년 전 0

dwax1324 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말