9082_지뢰찾기

완전탐색으로 구현하다가 낭패 본 문제

11122 ####*

위 쪽의 입력은 자신의 인덱스의 좌, 자신, 우의 지뢰의 개수를 가르쳐준다.

입력의 윗 부분만 보면 된다. 

첫 번째 입력이 2인 경우

result[0] = 1, result[1] = 1 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번재 입력이 0인 경우

result[0] = 0, result[1] = 0 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번째 입력이 1인 경우

result[0] = 1, result[1] = 0 으로 세팅 한 후에

위의 재귀 동작을 수행 시켜서 마지막 인덱스의 답이 맞으면 넘어가고

틀리면

result[0] = 0, result[1] = 1으로 세팅 한 후에 

위의 재귀 동작을 수행 시키면 된다.

이렇게 하면 무조건 답이 나온다. 

범위가 100까지 이므로

완전탐색의 최악의 경우 2^100이므로 절대 완전탐색을 하면 안되는 문제였다. 

분명 규칙을 찾아야 하는 문제였는데, 

백트래킹으로 풀려다가 계속 안 풀린 문제였다. 

계산해봐서 절대 시간안에 풀수 없는 문제이면 완전탐색 시도를 하면 안되고 무조건 규칙을 찾아야 한다는 것을 깨달았다.