(스포) 문제의 풀이 로직이 담겨있는 글일 수 있습니다.

안녕하세요,

먼저 게시판을 읽고 조금더 생각을 하면서 문제를 맞히긴 했지만, 

그럼에도 불구하고 초기에 짠 코드의 로직이 어디서 이상한지/ 또는 어떤 반례가 있을지 여쭙고 싶어 질문을 올렸습니다.

변수:

subeen_dist 배열은 수빈이가 최단 거리에 그 node를 방문하는 시간입니다.

sister_dist는 여동생이 node를 방문하는 시간이며,

temp_dist는 최단거리는 아니지만 sister_dist와의 시차가 짝수인 시간 배열입니다.

함수:

sister_move함수는 여동생이 움직이는 이동시간을 표시한 함수입니다.

b

BFS는 거리 순으로 노드들을 방문한다고 알고 있습니다. 

그러나 이 문제는 일반적인 BFS 문제들과는 달리, 이 문제는 한번 방문한 node를 다시 방문하는 경우까지 고려해주어야 하고,

먼저 도착한 수빈이가 여동생을 기다릴 수 있다고 생각했습니다.

그러나 기다리는 시간에도 움직이긴 해야하기에, lag라는, (동생의 방문시간)-(수빈이의 최단방문시간)을 의미하는 변수를

선언했습니다.

lag가 짝수라면, 더 이상 고려할 필요가 없다고 생각했습니다. 

문제는 lag가 홀수인 경우인데, 

최단 시간보다는 좀더 걸리면서, 수빈이의 최단방문시간보다는 짧게 걸리는 배열이 필요하다고 생각했습니다.

그 배열이 temp_dist이고, 47번 줄부터 이를 선언하고 있습니다.

한 node는 여러번 방문될 수 있기에, temp_dist[node]의 값도 갱신이 될 수 있겠지만,

결과적으로 temp_dist[node]의 값이 여동생의 방문시간보다 작기만 하면 상관없다고 생각했습니다.

답 출력 방법의 경우, 결국 제때에 맞춰 수빈이와 여동생이 동시에 그 node를 방문하거나 수빈이가 먼저 방문했다가 왔다갔다하며 기다리는 구조이기에,  여동생의 시간을 출력하면 된다고 생각했습니다.

혹시 다른 반례 있으면 공유해주시면 감사하겠습니다.