글 읽기 - (반례요청, 설명있음)반례는 다 돌려봤는데 모두 정답과 일치했습니다.

ando0902 1년 전 0

k에서 i로 역추적 하면서 그래프를 구성하였고 완성된 그래프로 넓이 우선탐색으로 n에서k로 추적하는 방법을 사용하였습니다.

from collections import defaultdict, deque
n, k=map(int, input().split())
graph=defaultdict(set)
graph[k].add(k) # k->n으로 역추적
while n not in graph.keys(): # 딕셔너리의 키에 n 이 없으면
    lst=list(graph.keys()) # 딕녀서리의 키를 리스트로 바꿔서
    for i in lst:
        if i<n: # i가 n보다 작아진다면 더하는 방법밖에 없으므로 i와 n을 바로 연결시켜 차이를 더함
            graph[n].add(i)
        elif i%2==0 and n-i//2<i-n: # i가 2로 나누어 떨어지면서, n 과의 거리에 있어서 i 보다 i를 2로 나눈값이 더 가깝다면 i를 2로 나눔
            graph[i//2].add(i)
        else: # 나머지는 그냥 1을 더하거나 뺌
            graph[i-1].add(i)
            graph[i+1].add(i)
if n==list(graph[n])[0]: # n==k라면
    queue=deque([k])
    a=0
else: # n!=k라면
    visit=set([max(list(graph[n]))])
    queue=deque([max(list(graph[n]))])
    a=1 # 한번 방문하였으므로 1부터 시작
if max(list(graph[n]))<n: # while문에서 첫번째 조건에 해당할 때
    a+=n-max(list(graph[n]))-1 # 차이만큼 더함
    
while k not in queue: # queue에 k 가 나올 때까지
    a+=1 #queue 에 k가 없다면 +1
    for _ in range(len(queue)): #queue의 모든 요소 조사
        x=queue.popleft() #queue의 왼쪽부터 pop
        queue.extend(list(graph[x]-visit)) # 연결된 노드로 가면서 이미 방문했었으면 포함하지 않음
        visit.update(graph[x]-visit) # 방문한 곳 추가
    
print(a)

siyamaki 1년 전 2

반례입니다.

10007 98767
output:4338
answer:2343

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

문제

문제

출처

ICPC

(반례요청, 설명있음)반례는 다 돌려봤는데 모두 정답과 일치했습니다.

ando0902 1년 전 0

siyamaki 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말