백준 15649번(백트래킹)

최근에 기초적인 알고리즘을 공부하다가 백트래킹에 관한 내용을 알게 되었다.

여기서 백트래킹이란 가능한 모든 경우의 수를 생각해 보는 알고리즘으로 해를 찾는 도중에 막히게 되면 재귀함수를 사용하여 되돌아가서 다시 해를 찾아가는 기법이다.

아래는 백트래킹에 관한 문제인 백준 15649번 문제이다.

위의 코드는 해당문제에 대한 코드이다.

간단하게 설명해 보기 위해서 N=3, M=2라고 가정하고 코드를 분석해 보겠다.

1.ans(정답 리스트 추가할 공간), v(해당 숫자를 사용했는지 확인하는 숫자)를 설정해 주었다.

2.dfs(0, [])은 초기의 n의 크기를 0으로 설정하고 lst 또한 초기화시켜서 함수에 투입한다.

3. 먼저 for문을 돌게 된다. 여기에서 v [1]=0이기 때문에 v [1]=1로 설정하고 다음 dfs(1, [1]) 함수로 넘어간다. 그에 따라 v를 보게 되면 v=[0,1,0,0] 임을 알 수 있다. 

여기서 다시 for문을 돌리게 되면 v [1]=1이기 때문에 넘어가고 v [2]=0이기 때문에 v [2]=1는 1로 바뀌고 다음 dfs(2, [1,2]) 함수로 넘어간다. 여기서 v=[0,1,1,0]이다.

dfs(2, [1,2])이기 때문에 종료조건을 만족하게 되고 해당 리스트를 ans에 추가해 주고 return을 통해 이전 함수 dfs(1, [1])로 돌아가게 된다. 그러나 아직 v [2]=1이기 때문에 for문을 돌리게 되었을 경우에 dfs(2, [1,3])의 값을 가지고 다시 list에 추가되어 return 하게 된다.

return을 하게 될 경우 dfs(1, [1])로 이동하게 되고 여기에서 for문이 3까지 다 돌았기 때문에 dfs(0, [])으로 초기화가 되게 된다. 또한 다음의 이동은 dfs(1, [2])에서부터 시작하여 계속하여 함수가 진행되게 된다.

 

백트래킹은 쉽게 생각하면 for문안에 for문을 계속 넣는 형태로 생각하면 편하다.