저는 재귀로 모든 경우 다 탐색해보는 방법으로 접근을 했는데, 90% 정도에서 시간초과가 나서 해매다가 https://www.acmicpc.net/board/... 이 질문답변 글을 읽고 제 원래 코드에서 그냥 도착지점이 1이면 바로 0을 출력하도록 코드를 수정해서 한번 제출해봤습니다.
그렇게 하니까 바로 통과가 되더라구요...
일단 제 코드의 로직을 설명드리자면
- 출발 위치와 이전 파이프의 type(0은 가로,1은 세로,2는 대각선)을 받음.
- type에 따라서 다음 도착 위치를 검사하고 막혀있지 않고, 맵을 넘어가지 않는다면 해당 위치에서 다시 탐색(재귀)
- 도착점에 도착하면 전역변수를 1 늘려주고 리턴
이런 방식으로 접근했었는데 제 생각에는 이 방식으로 접근하면 16 크기에서 전부다 벽이 없을때 가장 시간이 오래 걸려야 한다고 생각했거든요.
왜냐하면 벽에 막힌 경우는 아예 재귀가 실행조차 안되고 넘어가니까 당연히 스택 수가 줄어들고 계산도 더 빨라질거라 생각했어요.
그런데 저 반신반의로 테스트해본 도착지점이 0일때의 경우 체크를 해주니까 이렇게 시간초과가 해결되는게 이유가 너무 궁금해서 질문 올립니다.
맨 끝이 1로 막혀 있을때 16 크기에서 전부 벽이 없을때보다 시간이 더 오래 걸리는 경우가 뭐가 있을까요...?
ghddhksduq 2년 전
저는 재귀로 모든 경우 다 탐색해보는 방법으로 접근을 했는데, 90% 정도에서 시간초과가 나서 해매다가
https://www.acmicpc.net/board/...
이 질문답변 글을 읽고 제 원래 코드에서 그냥 도착지점이 1이면 바로 0을 출력하도록 코드를 수정해서 한번 제출해봤습니다.
그렇게 하니까 바로 통과가 되더라구요...
일단 제 코드의 로직을 설명드리자면
- 출발 위치와 이전 파이프의 type(0은 가로,1은 세로,2는 대각선)을 받음.
- type에 따라서 다음 도착 위치를 검사하고 막혀있지 않고, 맵을 넘어가지 않는다면 해당 위치에서 다시 탐색(재귀)
- 도착점에 도착하면 전역변수를 1 늘려주고 리턴
이런 방식으로 접근했었는데 제 생각에는 이 방식으로 접근하면 16 크기에서 전부다 벽이 없을때 가장 시간이 오래 걸려야 한다고 생각했거든요.
왜냐하면 벽에 막힌 경우는 아예 재귀가 실행조차 안되고 넘어가니까 당연히 스택 수가 줄어들고 계산도 더 빨라질거라 생각했어요.
그런데 저 반신반의로 테스트해본 도착지점이 0일때의 경우 체크를 해주니까 이렇게 시간초과가 해결되는게 이유가 너무 궁금해서 질문 올립니다.
맨 끝이 1로 막혀 있을때 16 크기에서 전부 벽이 없을때보다 시간이 더 오래 걸리는 경우가 뭐가 있을까요...?