단순 계산으로도 dfs는 좋은 방식이 아니라는 걸 알 수 있습니다.
가로로 배치하는 거를(16, 9/ 1, 2에 동시에 배치하는 형태) 제외해도
각각의 세로 두 칸을 한 번에 배치하거나/각각 하나씩 배치하는 두 가지 방법이 있기 때문에
2^N의 시간이 걸립니다.
물론 가로로 배치하는 걸 고려하면 더 늘어날거고, 최적화를 하면 또 줄어들거라 정확하진 않겠지만
매우 가짓수가 많은 거는 사실이죠.
최적화를 잘 한다면 가능할지는 몰라도, 정말 해가 없을 케이스를 잘 골라내지 않는 이상은 힘들겁니다.
yousrain 4년 전
재귀호출을 이용한 dfs 아이디어로 구현하여 문제를 풀었는데 시간초과가 계속 나와서 질문드립니다.
간단하게 알고리즘을 말씀드리면
1) 각 섹터 별로 점수를 저장한 int arr[2][10001]
해당 섹터에 부대를 배치했는지 여부를 체크하는 bool visited[2][10001]로 자료구조를 정했습니다.
2) [0][1]부터 함수를 시작합니다.
a. 전달받은 파라미터가 x = 1, y = N 인 경우
더이상 dfs를 수행하지 않고 결과값을 저장하는 전역변수 result를 조건에 맞게 갱신.
b. 전달받은 파라미터 섹터의 visited값이 true인 경우 --> 다음 dfs 바로 호출
c. 전달받은 파라미터가 그 외인 경우
경우 1. 현재 섹터와 왼쪽 섹터의 병력 합이 W(침투병력)보다 작은 경우
--> 두 섹터의 visited값이 false라면 두 값을 true로 바꿔주고 다음 dfs 호출
-다음 dfs 호출은 y값을 1 증가시키는 값입니다. 예) [0][3] 다음은 [0][4], [0][N] 다음은 [1][1]
질문 ) 여기서 나름대로 방법을 써서 불필요한 dfs연산을 줄였는데 계속 시간초과가 나옵니다 ㅠㅠ
혹시 재귀호출로는 절~~대로 정답을 구할 수 없는 건가요??