백준 1107 DFS로 문제 풀기

목표: 백준 1107 문제 풀기

환경: mac OS Mojave 10.14, Visual Studio 2015

로직

dfs(버튼을 누른횟수, 채널) 이란 함수를 정의해서 모든 경우의수를 계산하여 풀이했습니다.

버튼을 누른횟수가 찾으려는 수의 자리수보다 크면 종료해야됩니다. 질문 검색을 통해 알아낸 결과, 이동하려는 채널보다 큰 수에서 - 버튼을 통해서 이동하는게 빠를 수도 있습니다. 그래서 재귀 종료조건을 아래와 같이 만들었습니다.

if (idx > sz+1) {
  return;
}

dfs를 하면서 자리수를 앞에서부터 선택을 해줍니다. 1234면 천자리, 백자리, 십자리, 일자리 순으로 선택합니다.

해당 자리수에 누를 버튼을 for문을 돌면서 고장난 버튼이 아니면 버튼을 누르고 버튼을 누른 결과를 갱신하여 인자로 넘겨줬습니다.

for (int i = 0; i < 10; i++) {
  if (!error[i]) {
    int nNum = curNum * 10 + i;

    dfs(idx+1, nNum);
  }
}

시간복잡도는 O(10^자리수)입니다.

SourceCode