yih9329   5년 전

  1. bfs로 풀었는데 이렇게 풀 경우 동생이 특정지점 x에 가기 전에 수빈이가 먼저 x에 가게되면 방문표시가 돼서 답을 제대로 출력할 수 없는 문제가 있었습니다. 방문체크를 안하고 bfs를 하면 당연하겠지만 시간초과가 나서 이 방법은 접었습니다.

2. 단위시간마다 동생의 위치를 업데이트하고, 시간이 지나기 전에 수빈이가 위치할 수 있는 모든 공간을 set에 저장해뒀습니다. 동생의 위치가 다음턴에 x라고 하면 잡힐 수 있는 경우는 수빈이가 x-1, x+1, 2x에 있을 때 뿐이므로 set자료구조의 contains를 이용하여 셋 중에 해당되는 값이 있는지를 확인했습니다. 하지만 이 경우에는 시간초과가 나서 이 방법또한 접었습니다.

3. 2번의 방법과 비슷하게 시도했는데 set자료구조를 사용하지 않고 list에 수빈이의 위치를 저장해두고 정렬을 한 후, 이진탐색으로 x-1, x+1, 2x에 해당하는 값이 있는지 확인했습니다. 2번의 경우와 비교해서 속도가 근소하게 빨라지긴했으나 여전히 시간초과가 납니다.

제 머리로는 더이상 어떤 방법을 써야될지 모르겠습니다.ㅠㅠ 

시간초과가 나지 않으려면 어떤식으로 접근해야할까요? 도움부탁드립니다.

djm03178   5년 전

이 문제의 핵심적인 스포일러입니다. 스포일러를 원하지 않으시는 분은 뒤로가기를 눌러주세요.

*** 스포일러 ***

어떤 점 x에 t초에 도달할 수 있다면, t+2, t+4, t+6, ... 에도 x에 도달할 수 있습니다. 좌우로 한 번 왔다갔다하면 다시 제자리로 돌아오기 때문입니다. 즉, 짝수초에 x에 도달하는 최단 시간과 홀수초에 x에 도달하는 최단거리를 각각 구하면 됩니다.

yih9329   5년 전

잘 이해가 안되는데요.. 

어찌됐건 홀수초와 짝수초 중에 빨리 찾는 쪽이 답이 되는 거잖아요?

둘을 나눠서 처리하는게 의미가 있나요?

제가 위에서 말씀드린 접근방식자체가 틀린건가요?

djm03178   5년 전

2번 접근 방법의 경우 동생이 움직이는 시간은 최대 약 700초이기 때문에, 700초마다 최대 50만 개의 점을 set에 담고 contains로 찾는 것은 O(1) 접근 시간을 가지는 HashSet을 가정해도 3억 5천으로 시간 내에 통과할 수 없습니다.

3번 접근 방법 역시 정렬하는 데에 50만log50만을 700번 반복해야 하기 때문에 더 느립니다.

홀수초와 짝수초를 나누는 것의 의미는 예를 들어 홀수초를 저장하는 visited에 7이라는 값이 이미 들어가있다면 이후 홀수초에서 7을 방문할 수 있다고 하더라도 7을 큐에 넣지 않는다는 의미입니다. 그래서 50만 개의 점은 각각 많아야 2번씩 큐에 들어가고(홀수초일 때 한 번, 짝수초일 때 한 번) 많아야 100만개의 정점만을 탐색하게 됩니다.

yih9329   5년 전

설명 감사드립니다! 이해는 했는데 막상 구현하니 틀렸다고 나오네요.

시간문제는 없어진것 같은데 이번엔 또 어디가 잘못된걸까요 ㅠㅠ

djm03178   5년 전

다음 칸이 c가 되는 경우 뿐 아니라, 이미 visit 처리가 된 칸에 c가 도달하는 경우에도 종료해줘야 합니다.

yih9329   5년 전

한번 방문한 곳은 지나간 후에도 동생이 그 지점에 방문하게 되면 찾을 걸로 치는 건가요?

djm03178   5년 전

그냥 방문이 아니라, "짝수초"에 방문한 적이 있고 동생이 그 점을 "짝수초"에 지나간다면 찾은 것으로 칠 수 있고, 마찬가지로 "홀수초"에 방문한 적이 있고 동생이 그 점을 "홀수초"에 지나간다면 찾은 것으로 칠 수 있습니다. 왜냐하면, "짝수초"에 어떤 점에 수빈이가 도달했다면 그 이후의 모든 "짝수초"에는 그 점에 도달할 수 있음이 보장되기 때문입니다. 위에서 설명드린 것을 다시 찬찬히 읽어보세요.

nill1024   4년 전

대단하네요 djm님

궁금한게 있는데

짝수 홀수 나누는 걸 어떻게 생각하신 건가요?

그냥 문제 보면 떠오르나요?

이런 문제 잘 푸려면 많이 풀어보는게 방법이겠죠....? ㅜㅜ

djm03178   4년 전

한 20분? 정도 생각한 것 같네요. 평범한 BFS로는 어려우니 규칙을 찾다 보니 보였어요.

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