jupiny   2년 전

아래와 같이 그리디(출발점의 위에서부터 최대한 위의 경로로 이동한다) 알고리즘과 백트래킹을 이용하여 문제를 풀었습니다.

왠만한 예제들은 문제없이 통과하지만 시간초과 에러가 발생하네요.

아래의 알고리즘에서 시간복잡도를 개선할 수 있는 방법이 있을까요?

답변주시면 감사드리겠습니다. :D

cubelover   2년 전

아래와 같은 케이스에서 dfs(10, 18)이 호출되는 횟수가 매우 많습니다.

그런데 이전에 dfs(10, 18)의 값이 false였다면, 이후에도 dfs(10, 18)의 값은 false임이 확실합니다.

이 아이디어를 이용해서 시간복잡도를 O(RC)로 줄여보세요.

thexl   2년 전

현재 질문자분 코드의 시간 복잡도를 분석하면 출발점 하나를 체크할 때 O(3^C)만큼의 시간이 듭니다.

총 R개의 출발점이 있으므로 O(R * 3^C) => 최대 10000 * 3 ^ 500인데 계산해보면 3*10^242 정도 되네요.

Competitive Programming에선 1초에 대략 10^10 내외의 연산이 가능하다고 잡으므로 시간 초과가 나겠네요.


1) DP 사용하기

   Dynamic Programming을 사용하면 출발점 하나당 O(R*C)의 시간으로 해결할 수 있습니다. 

   느리긴 하지만 PASS는 되더라구요. (궁금하시면 PASS 하신 후 제 코드 참조 하시면 될 것 같습니다.)

2) Greedy

  더 빠른 코드는 질문자분 코드에서 "경로 표시 해제" 부분을 삭제하시면 됩니다. 그 이유는 다음과 같습니다.

    ① 성공했을 경우

       현재 경로로 파이프를 설치하여 해당 칸을 차지하게 되기 때문에 막습니다.

    ② 실패했을 경우

       현재 경로가 아니라 다른 경로로 이 자리에 와도 똑같이 실패할 것입니다. 그러므로 그냥 막은 상태로 둡니다. 일종의 DP로 볼 수 있겠네요.


추가) I/O 속도

 cin, cout의 속도가 느린 편입니다. 인풋(아웃풋)이 적을 때는 상관없지만 이 문제처럼 인풋양이 많을 때는 속도 저하의 원인이 될 수 있습니다.

 main에서 ios::sync_with_stdio(false); 호출 시 빠르게 인풋을 받을 수 있습니다.

jupiny   2년 전

@cubelover@thexl

두 분 모두 감사드립니다!!!

@cubelover 님이 말씀해주신 내용이 곧 @thexl의 답변의 2) Greedy 에 해당되는 내용인 것 같군요.

두 분이 의견을 듣고 19번 줄의 코드를 제거하였더니 바로 통과하였습니다. (그래도 시간복잡도가 여전히 크지 않을까 걱정했었는데 단번에 통과했네요.)

아마 DP에서 사용하는 일종의 메모이제이션과 같은 기능을 한 것 같습니다.


한 가지 궁금한 점은 이러한 풀이는 여전히 DP로 풀었다고는 할 수 없는 건가요..?

갑자기 백트래킹과 DP 개념 사이의 혼란이 오네요....ㅠㅠ

cubelover   2년 전

백트래킹과 DP를 정의하기 나름이지만, 보통 백트래킹은 상태 공간을 들어가다가 더 이상 진행할 수 없을 때 다시 되돌아 나오면서 탐색하는 '탐색 방법'의 한 종류를 가리키고, DP는 부분 문제의 답을 구해서 테이블에 기록해 둔 뒤 더 큰 문제를 해결하는 '문제 해결 기법'의 한 종류를 가리킵니다. 따라서 백트래킹이면서 DP일 수도 있고 둘 중 하나에만 속할 수도 있습니다.

질문자님께서 푸신 방법은 백트래킹에 메모이제이션을 한 것이라고 볼 수 있습니다. 부분 문제의 답을 구해서 기록해 둔 뒤 더 큰 문제를 해결하는 방식이라고 보기에는 다소 어려워서 보통 DP라고 부르지는 않지만, 이런 방식을 DP라고 하는 분도 있어서 그렇다 아니다라고 말씀드릴 수는 없을 것 같습니다.

jupiny   2년 전

@cubelover

친절한 설명 감사드립니다. 많은 도움이 되었습니다!!! :)

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