[BOJ][15651번] N과 M (3) (백트래킹)

안녕하세요 Dibrary입니다.

이번에 정리할 문제는 백트래킹을 사용해서 풀어야 하는? (백트래킹을 쓰기 좋은) 문제입니다.

개인적으로 백트래킹을 좀 어려워해서 정리해두고자 합니다.

15651번: N과 M (3)

---

이 문제를 보자마자 처음 든 생각은 '사용한 숫자를 또 쓸 수 있다니' 였습니다. 즉, 사용한 숫자와 사용하지 않은 숫자의 구별을 할 필요가 없는 셈이죠. 

이 문제를 풀 때 중요한 것은 '길이를 맞추는 것'과 '만들 수 있는 모든 경우'를 구해야 하는 것이죠.

길이 맞추는거야 갯수 세거나 하면 될거라 보는데, '모든 경우' 이게 문제죠.

 

숫자가 3개 있다고 가정할 때, 모든 경우를 따지려면 먼저 111부터 시작하는게 좋죠.

이렇게 말이죠. 그러면 사실상 우리에게 중요한 것은 3번째에서 1,2,3을 도는 게 중요합니다.

만일 1, 2로 가더라도 1,2,1 / 1,2,2 / 1,2,3 이렇게 3번째에서 1,2,3을 도는 게 중요하죠.

 

이걸 어떻게 구현해야하나.. 그게 가장 관건이었습니다.

 

---

코드는 아래와 같습니다.

코드는 재귀를 사용했습니다. 근데 잘 살펴보면 대부분의 백트래킹은 재귀를 많이 쓰더군요.

위 코드에서 if로 시작되는 부분은 '마지막에 도착하면 실행되는 부분'입니다. level == m 이라고 된걸 봐서는 level이 m이라는 숫자만큼 커질 것임이 보입니다. 이게 아까 얘기했던 '3번째'인지 아닌지를 확인하는 부분입니다.

중요한 것은 for문 내부의 코드입니다. 대부분의 백트래킹 코드가 이와 비슷한데,

임시 변수에 data[i]를 추가하고 재귀로 다시 들어갑니다. 여기서! level + 1을 해 주는것 보이시죠? 이게 중요합니다.

그리고, 재귀로 들어간게 끝나면 result.pop( )으로 넣었던 값을 꺼냅니다. 

 

말로만 하니 좀 어려운데, 1,2,3 예시에서 첫 번째만 설명해보자면,

1. 처음에 data[i]는 1일거고, result에 추가됩니다. 그리고 재귀로 넘어갑니다. (level=1)
2. 그 다음에 data[i]는 1일거고, result에 추가됩니다. 그리고 재귀로 넘어갑니다. (level=2)
3. 그 다음에 data[i]는 1일거고, result에 추가됩니다. 그리고 재귀로 넘어갑니다. (level=3)

여기서 level == m(=3)과 같기 때문에 조건문으로 빠집니다. 그래서 1,1,1이 제일 먼저 출력되고 return이 이뤄집니다.

근데, 이 return은 level=3에 해당하는 for문 중에 data[i]가 1인 경우에만 return한 것입니다.

for문은 2와 3까지 돌기 때문에, 그 다음에 다시 data[i]는 2가 되고 (level=3) 재귀로 넘어갑니다. 이번에도 level == m(=3)이므로 1,1,2가 출력되고 return이 됩니다.

 

이런 방식으로 순회하는 것이 백트래킹입니다. 

얼핏 보면 전체 완전탐색 같은데, 1,1,1까지 들어간 이후에 level=3에서 2,3만 찾고 더 이상 찾을 수 없으니 바로 전 단계로 되돌아온다는 의미죠.