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

nocturne07 2년 전 0

if d[y] > -1 : continue

부분을

'''

if d[y] > -1:

d[y] = min(d[y], d[x]) if teleport[x] else min(d[y], d[x] + 1)

continue

'''

로 바꿔주면 통과하긴 하는데 저 부분이 왜 필요한지 이해가 되지 않아서 반례를 보면서 이해하고 싶습니다.

n, m = map(int, input().split())
a = [[] for _ in range(101)]
teleport = [False]*101 # 뱀이나 사다리의 시작점인지 여부

for _ in range(n):
    x, y = map(int, input().split())
    teleport[x] = True
    a[x].append(y)

for _ in range(m):
    u, v = map(int, input().split())
    teleport[u] = True
    a[u].append(v)

for i in range(1, 101):
    if not teleport[i]:
        for j in range(1, 7):
            if i+j < 101:
                a[i].append(i+j)

q = [] # 먼저 처리하는 큐
nq = [] # 다음으로 처리하는 큐
d = [-1]*101

q.append(1)
d[1] = 0

while q:
    x = q.pop(0)

    for y in a[x]:
        if d[y] > -1: continue

        if teleport[x]:
            q.append(y)
            d[y] = d[x]
        else:
            nq.append(y)
            d[y] = d[x] + 1

    if not q:
        q, nq = nq, []

print(d[100])

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

문제

문제

출처

ICPC

반례 부탁드립니다 ㅜㅜ

nocturne07 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말