현재 질문자분 코드의 시간 복잡도를 분석하면 출발점 하나를 체크할 때 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 6년 전 3