글 읽기 - 두 코드의 차이점 반례가 뭐가 있을지 문의드립니다!

kc960923 2년 전 0

순서가 바뀌면 답이 틀리다 주석 부분 만 다른 두개의 코드가 있습니다.

첫번째는 통과고 두번째는 65퍼에서 틀렸습니다 인데 혹시 두코드의 차이점 반례가 뭐가 있을지 문의드립니다

from collections import deque

Max = 100001
cnt = [0]*Max
n,k = map(int,input().split())
def function():#bfs사용
    q = deque()
    q.append(n) #현재위치 n을 q에 삽입
    while q:
        now = q.popleft() #현재위치
        if now == k: #현재위치가 동생위치랑 같으면 현재위치까지오는데 걸린 카운트 출력
            print(cnt[now])
            return
        for _next in (now+1,now-1,now*2): #순서가 바뀌면 답이 틀리다.
            if 0<= _next <Max and not cnt[_next]:
                cnt[_next] = cnt[now]+1
                q.append(_next)
function()
############################################################################
from collections import deque

Max = 100001
cnt = [0]*Max
n,k = map(int,input().split())
def function():#bfs사용
    q = deque()
    q.append(n) #현재위치 n을 q에 삽입
    while q:
        now = q.popleft() #현재위치
        if now == k: #현재위치가 동생위치랑 같으면 현재위치까지오는데 걸린 카운트 출력
            print(cnt[now])
            return
        for _next in (now*2,now+1,now-1): #순서가 바뀌면 답이 틀리다.
            if 0<= _next <Max and not cnt[_next]:
                cnt[_next] = cnt[now]+1
                q.append(_next)
function()                    

sjyfantasy 2년 전 1

점프한 것이 선순위에 있으면

2 -> 4로 간 것이 먼저 적용이 되었다가

2-> 3->4로 간 것이 카운팅 되지 않을까요

sjyfantasy 2년 전 1

원래 있던 cnt값이랑 다음에 들어갈 cnt 값을 비교해서 낮은 값을 넣는 식으로 한다면 문제 없어 보입니다.

kc960923 2년 전 0

아 맞네요... 상세한 설명감사드립니다!

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

문제

문제

출처

ICPC

두 코드의 차이점 반례가 뭐가 있을지 문의드립니다!

kc960923 2년 전 0

sjyfantasy 2년 전 1

sjyfantasy 2년 전 1

kc960923 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말