글 읽기 - 반례 부탁드립니다.

fox9101 3년 전 0

bfs로 풀려고 했습니다. 초기 큐에 1,2,3,4,5,6을 집어넣고 돌립니다.(혹시 1,2,3,4,5,6중에 뱀이나 사다리에 해당하는 경우에는 해당하는 숫자를 집어 넣습니다.) 해당 숫자까지 가는 거리를 계산해서 이전거리+1보다 큰 경우에만 업데이트 시킵니다. 뱀이나 사디리에 해당하는 숫자는 중간 숫자 무시하고 최종 숫자만 비교해서 업데이트 시킵니다.

고수님들의 조언 부탁드립니다.

import sys
read = lambda : sys.stdin.readline()

n, m = map(int, read().split(" "))
dist = [-1] * 101
dic = {}
for _ in range(n+m):
    u, v = map(int, read().split(" "))
    dic[u] = v
queue = []
for i in range(1, 7):
    if i in dic:
        dist[dic[i]] = 1
        queue.append(dic[i])
    else:
        dist[i] = 1
        queue.append(i)

while queue:
    x = queue.pop(0)
    if x == 100:
        print(dist[100])
        break
    for i in range(1, 7):
        if 1<= x+i <= 100:
            if x+i not in dic:
                if dist[x+i] == -1 or dist[x+i] > dist[x]+1:
                    queue.append(x+i)
                    dist[x+i] = dist[x]+1
            else:
                xi = dic[x+i]
                if dist[xi] == -1 or dist[xi] > dist[x]+1:
                    queue.append(xi)
                    dist[xi] = dist[x]+1

fox9101 3년 전 1

문제를 잘못 읽었습니다. 0에서 주사위 던지는 줄 알았는데 문제 다시 읽으니 1에서 시작하는거였습니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다.

fox9101 3년 전 0

fox9101 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말