7-C
316
59 asked
http://boj.kr/3c3c09b8b7994f2aa915ac2c4916f166
dfs를 사용하여 visited도 똑같이 적용하여 풀었는데 6%에서 시간초과가 나네요... 큰돌님 코드도 dfs 기반의 코드 같은데 혹시 시간초과가 나는 이유가 있을까요..?
Answer 2
0
답변 감사드립니다 큰돌님! 자소서랑 포폴에 치여서 코테를 좀 놨더니 충격적인 결과가 나와서 다시 코테 해보고 있습니다!!ㅋㅋ
알아봐주셔서 감사하고 다시 알고리즘 다잡고 해보겠습니다. 답변 감사드립니다!
0
안녕하세요 자르트님 ㅎㅎ
오랜만이네요. ㅎㅎ
코드 살펴봤는데 이상한점이 없는데...
이상하네요.
기저사례도 괜찮고.
for (int i = 0; i < 4; i++) {
int ny = y + dy[i] * board[y][x];
int nx = x + dx[i] * board[y][x];
// 방문한적 있으면 사이클 가능해 무한번 이동 가능
if (0 <= ny && ny < n && 0 <= nx && nx < m) {
if (visited[ny][nx] == 1) {
cout << -1 << '\n';
exit(0);
}
dfs(ny, nx, cnt + 1);
}
// 바깥으로 나가더라도 횟수 1회 증가 후 최댓값 갱신
else {
result = max(result, cnt + 1);
}
}지금 보시면 ny, nx에 따라 사이클 처리, dfs가 더 발생하는 것도 아니고...
시간초과가 날만한 불필요한 부분이 없네요..
오히려 제 코드보다 함수호출이 덜합니다. 함수호출에 의한 시간초과가 나지는 않는 것 같고 제 생각에 어떤 반례에서 걸리는 거 같습니다.
이 문제가 좀 어려운게 반례를 만들기가 굉장히 어려워서... 일단은 몇개 넣고는 있는데 잘 안되네요.
이부분 제가 좀 더 보고 반례 찾으면 다시 답변 드리겠습니다.
감사합니다.
2주차 개념#12 트리 순회
0
8
2
백준사이트가 종료된다고 합니다.
0
200
2
백준 서비스 종료
9
633
1
sk 하이닉스 코테 대비
0
346
2
3-G 최댓값 질문
0
46
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
77
2
3-I 코드 질문드립니다.
0
59
2
3-N 질문 있습니다.
0
63
2
학습방법
0
98
2
4-H 질문 있습니다 (코드 리뷰)
0
65
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
161
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
68
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
62
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
48
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
66
2
함수별 시간복잡도
0
71
2
3-h 질문입니다.
0
47
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
51
2
1-I 문제 질문 드립니다.
0
74
2
2-P 질문입니다.
0
55
1
mac에서 시작하기 관련
0
86
2
5-Q 질문
0
62
2
풀이 코드 질문
0
62
2
맞왜틀
0
67
2