백준 15649 - N과 M (1) (Python)

https://acmicpc.net/problem/15649 

15649번: N과 M (1)

백트래킹에 대해 처음 알게 된 문제.

지난 토요일 카카오 코테에서 못 풀고 시간만 날린 문제가 bfs가 아닌 백트래킹 문제임을 알게 되었다.

문제는 간단하게, 1부터 N까지의 자연수 중 M개로 이루어진 중복순열을 다 구하는 것이다.

​

백트래킹의 개념은 굉장히 단순하다. 결국엔 다 해보는 것과 다를 바 없지만, 하다가 아닌 것 같은 때 그만 둔다.

​

1. dfs의 탈출 조건은 s라는 현재 배열의 길이가 m, 즉 내가 만들고자 하는 순열의 길이와 같을 때이다.
2. 같아질 때까지, 우리는 1부터 n까지 s에 숫자를 넣는다.
3. 이때, visited를 따져가며 만약에 방문한 적이 있다면 건너뛴다.
4. 방문한 적이 없다면 s에 넣고, 크기가 s가 될때까지 이걸 반복한다.

​

4,2를 예시로 생각해보면,

처음에는 s에 아무것도 없으니 for문으로 들어간다. 처음에는 1이 visited가 아니므로 s에 1을 넣고 visited[1]을 True로 바꿔준다. 이렇게 바꿔주면 다음 dfs를 돈다.

이때는 visited[1]이 True이므로 바로 2를 검사하고, 이때 visited[2]는 False이니 s에 2를 넣고 visited[2]를 True로 바꿔준다. 또 다음 dfs를 도는데, 이 때는 길이가 2이니 1 2를 출력한다.

돌던 dfs를 마저 돌자. s.pop()은 아까 돌던 그 상태에서 2를 pop하고 visited를 False로 바꿔주고, for문의 차례에 따라 3을 봐주러 넘어간다. 그러면 1 3을 출력하고, 1 4를 출력하고...를 반복하는 것이다.

​

너무 생소하다. Class 4에 이런 문제들이 모여 있는 것 같으니 계속 연습해야겠다.