올라와 있는 반례를 시도해봤는데요. 

다맞았습니다.

그런데 왜틀릴까요?

반례줌찾아주세요!

qwer9412   11달 전

4 12

답이 1 이 나와야 합니다.

(4, 0) -> (3, 1) -> (6, 1) -> (12,1) 이 동선이 해답인데요.


(4,0) -> (5,1) -> (6,2) 이 동선에 의해 (6,2) 가 먼저 로직를 돌테고 이때 visit[6]을 true로 만들겠죠.

그럼 (4,0) -> (3,1) -> (6,1) 이 동선에 의해 else if 로직을 탈때는 이미 visit[6] 이 true이니 (12,1) 동선을 타지 못하게 됩니다.

이해가 잘 안가신다면 손으로 queue 에 들어갈 값들의 순서를 써보시면 아실수 있을거에요.

leeingyun96   11달 전

if(now==k){

res=min(res,times);

여기에 포함되면 설령 visited가 이미 true라고 하더라도 갱신이 되었다는 뜻이니 3가지 간선을 다시 돌려야 합니다. 

"4 6"은 q안에 들어간 두 개의 6중 느린 6만 간선을 돌리더라도 빠른 6으로 res가 갱신이 되니 답이 나오지만, "4 12"는 느린 6만 간선이 뻗어나갔고 빠른 6으론 갱신인 됐을지언정 간선이 뻗질 않으니 답이 안 나옵니다.


이것과는 별개로 0-1 bfs로서든 다익스트라로서든 정답 구현과는 거리가 머니 찾아보시는 걸 추천합니다.

감사합니다!

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