ghddhksduq   2년 전

저는 재귀로 모든 경우 다 탐색해보는 방법으로 접근을 했는데, 90% 정도에서 시간초과가 나서 해매다가 
https://www.acmicpc.net/board/...
이 질문답변 글을 읽고 제 원래 코드에서 그냥 도착지점이 1이면 바로 0을 출력하도록 코드를 수정해서 한번 제출해봤습니다. 

그렇게 하니까 바로 통과가 되더라구요...

일단 제 코드의 로직을 설명드리자면

- 출발 위치와 이전 파이프의 type(0은 가로,1은 세로,2는 대각선)을 받음.

- type에 따라서 다음 도착 위치를 검사하고 막혀있지 않고, 맵을 넘어가지 않는다면 해당 위치에서 다시 탐색(재귀)

- 도착점에 도착하면 전역변수를 1 늘려주고 리턴


이런 방식으로 접근했었는데 제 생각에는 이 방식으로 접근하면 16 크기에서 전부다 벽이 없을때 가장 시간이 오래 걸려야 한다고 생각했거든요.

왜냐하면 벽에 막힌 경우는 아예 재귀가 실행조차 안되고 넘어가니까 당연히 스택 수가 줄어들고 계산도 더 빨라질거라 생각했어요.

그런데 저 반신반의로 테스트해본 도착지점이 0일때의 경우 체크를 해주니까 이렇게 시간초과가 해결되는게 이유가 너무 궁금해서 질문 올립니다.

맨 끝이 1로 막혀 있을때 16 크기에서 전부 벽이 없을때보다 시간이 더 오래 걸리는 경우가 뭐가 있을까요...?

rich1055   2년 전

아래와 같은 코드를 실행해보세요 

마지막이 1일때가 더 빨리 작동합니다. 


정답처리되는 이유는 데이터가 빈약해서 그런거 같습니다.

ghddhksduq   2년 전

저도 그래서 당연히 마지막이 1일때가 더 빠르게 작동할 것 같은데, 왜 마지막이 1인 케이스를 예외처리해주니까 시간초과가 해결되는 건지가 궁금합니다....ㅠ

rich1055   2년 전

원래는 그렇게 해도 시간초과가 되야하는데 

채점할때 사용하는 데이터에 n = 16이고 모두 0인 데이터가 없을경우

시간초과가 나서 틀려야할 코드가 맞을 가능성도 있습니다.

ghddhksduq   2년 전

아하 그런가보네요... 감사합니다~!

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