tmvld9   2년 전

테스트케이스도 맞게 나오고 시간초과나는 반례도 답이 잘 나오는데요, 어느 부분이 틀렸나요..?!

djm03178   2년 전

여러 불필요한 코드들이 있어서 그렇습니다.

  1. 46~49번째 줄의 의도는, "s보다 작은 정점들이 갈 수 있는 곳들은, 이미 계산을 했으니까 그대로 사용하면 되겠지" 인 것으로 보입니다. 그러나, 이 논리에는 여러 문제가 많습니다. 예를 들면 아래의 케이스가 있겠습니다. 배열은 레퍼런스이기 때문에 3번 정점이 1번 정점에 도달하는 순간 1번 정점과 서로 같은 배열을 공유하게 되고, 그래서 이후 2번 정점에 방문한 기록은 마치 1번 정점도 같이 방문한 것처럼 표시됩니다. 게다가 1번 정점에는 방문했다는 기록 자체가 남질 않습니다. (1번에서 1번으로 가는 경로는 없기 때문이죠.) 뿐만 아니라 a보다 작은 정점을 통해 도달할 수 있었던 다른 정점이 있는데도 그 정보를 덮어쓰고 마는 케이스도 얼마든지 만들 수 있습니다.
  2. visit는 2차원일 필요가 없습니다. 한 번의 탐색에서 하나의 정점은 두 번 이상 거쳐갈 필요가 없기 때문이죠. 한 번의 탐색에 n개의 정점만 거쳐가면 되는데, 지금 방법으로는 최대 n^2번의 dfs 호출이 일어납니다.
  3. 2번이 프로그램의 답 도출에 영향을 일으키는 건 42번째 줄 때문입니다. n개가 넘는 정점을 탐색했다면 탐색을 종료해야 하는데, n개의 간선을 탐색했을 뿐인데 더 나아가지 않고 종료해버릴 수도 있으니까요. 애초에, 과연 이런 처리가 필요할까요? 정말로 모든 정점을 탐색했다면 44번째 줄의 조건에 걸려들 일이 전혀 없을 텐데, 굳이 수작업으로 이런 처리를 할 필요는 없습니다. 물론 약간의 퍼포먼스 향상이 있을 수도 있겠지만 반대로 오버헤드일 수도 있겠고요. 수작업으로 예외 처리를 해주려다가, 도리어 반례를 만들어내는 상황이라고 할 수 있겠습니다.

마지막으로 한 가지 부탁을 드리자면, 질문을 올릴 때 꼭 써야 할 내용은 테스트 케이스가 맞게 나온다거나 반례가 잘 나온다거나 하는 게 아닙니다. 내 코드가 뭘 하는 코드인지 설명하는 게 제일 중요합니다. 왜 46번째 줄에서 굳이 저렇게 잘라내는지, 이해하는 데에 한참 걸렸습니다. 자신의 논리가 정당하다고 생각한다면 그 논리를 설명해야 하는데, 마치 당연히 써야 하는 코드인 것처럼 아무 설명 없이 두면 답변자가 코드의 결함을 찾아내는 게 훨씬 힘들겠죠? 앞으로는 질문을 올릴 때 코드에 대한 설명도 함께 쓰면서, 내 생각이 정말 맞는지도 다시 한 번 되돌아보는 시간을 가졌으면 좋겠습니다.

tmvld9   2년 전

djm03178님


죄송합니다. 제가 마음만 급했네요. 다음부터는 코드를 좀 더 세밀하게 분석하고 판단하는 시간을 가져야겠습니다. 

정말 친절한 설명 너무너무 감사합니다. 

  

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