인프런 커뮤니티 질문&답변

답변 감사드립니다 큰돌님! 자소서랑 포폴에 치여서 코테를 좀 놨더니 충격적인 결과가 나와서 다시 코테 해보고 있습니다!!ㅋㅋ

알아봐주셔서 감사하고 다시 알고리즘 다잡고 해보겠습니다. 답변 감사드립니다!

안녕하세요 자르트님 ㅎㅎ

오랜만이네요. ㅎㅎ

코드 살펴봤는데 이상한점이 없는데...

이상하네요.

기저사례도 괜찮고.

	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가 더 발생하는 것도 아니고...

시간초과가 날만한 불필요한 부분이 없네요..

오히려 제 코드보다 함수호출이 덜합니다. 함수호출에 의한 시간초과가 나지는 않는 것 같고 제 생각에 어떤 반례에서 걸리는 거 같습니다.

이 문제가 좀 어려운게 반례를 만들기가 굉장히 어려워서... 일단은 몇개 넣고는 있는데 잘 안되네요.

이부분 제가 좀 더 보고 반례 찾으면 다시 답변 드리겠습니다.

감사합니다.