[Python][백준/BOJ] 15649번 : N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

내 코드(1) - visited[] 안 쓰고 풀기

n, m = list(map(int, input().split()))

s = []

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    for i in range(1, n + 1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

 

내 코드(2) - visited[] 쓰고 풀기

n, m = list(map(int, input().split()))

visited=[False for _ in range(101)]
tmp =[]

def dfs():
    if len(tmp) == m:
        print(' '.join(map(str, tmp)))
        return
    
    for i in range(1, m+1):
        if not visited[i]:
            tmp.append(i)
            visited[i]=True
            dfs()
            visited[i] = False
            tmp.pop()
            
dfs()

 

dfs, 백트래킹

이해하느라 꽤 고생했던 문제이다.

구현 자체는 꽤 간단하지만, 코드를 잘 이해하는 것이 중요하다. 이 코드는 함수가 곧 답인데 함수를 뜯어보면

    if len(s) == m:
        print(' '.join(map(str, s)))
        return

우선 중단점을 만들어준다.(문제 조건 반영)

길이가 m인 수열을 만들어야 하므로 s의 길이가 m이면 return해서 재귀를 빠져나온다. return 도 중요한 역할이기 때문에 메모리 할당도 이해해야 한다. 

전체적인 흐름은 이렇게 된다. 만약 n=4, m=4일 때의 경우이다.

i=1	dfs1	s=[1]
i=2	dfs2	s=[1,2]
i=3	dfs3	s=[1,2,3]
i=4	dfs4	s=[1,2,3,4]
if문	dfs5	if문 만나서 return(dfs5 할당 메모리 반납)
pop	dfs4	s=[1,2,3]
pop	dfs3	s=[1,2]
i=4	dfs4	s=[1,2,4]
i=3	dfs3	s=[1,2,4,3]
if문	dfs5	if문 만나서 return(dfs5 할당 메모리 반납)
pop	dfs3	s=[1,2,4]
pop	dfs4	s=[1,2]
pop	dfs2	s=[1]
i=3	dfs3	s=[1,3]

 

1. 먼저 1부터 5까지 넣을 때, dfs1 dfs2 dfs3 dfs4 까지 가고, dfs5까지 간다.

2. dfs5에 갔을 때 s에는 [1, 2, 3, 4]가 들어간 상태이다. 이때 if문을 만나 길이가 4인 것이 걸리고, 값을 출력한 후 return한다. return은 dfs5라는 메모리 할당 공간을 return으로 뱉어낸다.

    for i in range(1, n + 1):
        if i not in s:
            s.append(i)
            dfs()
            #>>dfs()가 돌아오면 여기부터 다시 시작함. for문의 range 조심
            s.pop()

3. 그러면 dfs4로 돌아온다. dfs4는 현재 dfs()라는 함수까지 끝낸 상태니까 그 다음부터 시작하는데, 이제 s.pop() 을 한다. 그래서 s에서 pop으로 4를 뱉어낸다. s=[1.2.3]

4. dfs4()는 i=4 까지 돌았고 dfs라는 전체 함수는 할 일을 다했으니 함수 자체가 return된다.

5. 그러면 dfs3으로 돌아온다. 마찬가지로 dfs()라는 코드를 써서 dfs4를 불러냈던 전적이 있으니, 그 다음 코드부터 다시 이어가야한다. 그러면 s.pop()이고 3도 지워버린다. s=[1,2]

6. 이때 주의해야 할 점은 i=3일 때 dfs3이었다는 점이다. 그러면 반복문에서 i=3이었던 상태니까 다시 i=4가 남은 상태이다. 하지만 4는 현재 s에 존재하지 않는다. 그러면 넣어줘야 한다. s=[1,2,4]

7. 그러면 다시 dfs4가 되는데, 새로운 dfs는 반복문 i=1~4를 또 다시 반복해서 새롭게 돈다. s에는 이미 1,2가 있는 상태이므로 i=3일 때 3을 넣어준다. s= [1,2,4,3]

이해하는데 정말 많은 시간이 걸렸다. 앞으로 N과 M을 1부터 12까지 다 풀어봐야겠다.