백준 15649 -N과 M

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

15649번: N과 M (1)

 

 

못풀겠어서 다른 사람의 풀이법을 참고하여 해결하였음

 

해당 문제는 백트래킹 알고리즘의 기본 예제 문제이다.

그렇다면, 백트래킹이란 무엇일까?

백트래킹이란, 해를 찾는 도중 해가 아니어서 막히며, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

모든 경우의 수를 고려할 때 쓰이는데 흔히 다 알고 있는 트리 탐색의 경우, 그냥 해를 찾기 위해 계속 탐색만 할 뿐 막히면 되돌아가지는 않는다. 그래서 많은 시간과 메모리가 소모된다.

하지만 백트래킹은 중간에 막히면 더 이상의 진행을 하지 않아 이를 개선한 일종의 트리 탐색 알고리즘이다.

백트래킹은 일반적으로 DFS(깊이우선탐색)을 사용하여 풀이가 가능하며,  DFS와의 차이점은 가지치기를 한다는 점이다.

 

위 문제를 3가지 방법으로 풀이하려고 한다.

첫 번째 방법은 방문체크를 이용한 풀이법이고, 두 번째 방법은 스택을 활용한 풀이 방법이다.

사실상 두 방법 모두 리스트 스택을 활용하여 푼 방법이지만, 두 번째 방법은 첫 번째 방법에서 사용한 방문 리스트를 사용하지 않고도 풀 수 있기에 더 간단하다.

세 번째 방법은 모듈을 임포트하여 모든 조합을 구하는 함수를 사용한 풀이이다. 해당 풀이는 문제의도와 맞지 않고 파이썬에서만 적용할 수 있으므로 구현 코드만 올리고 마무리하려고 한다.

 

문제 요약)

n, m을 입력받아 m으로 자리 수를 정해놓고 각 자리에 숫자가 중복되지 않게 차례대로 나열하는 것

 

생각해야할 것)

1. 숫자가 중복되지 않게끔 나열해야한다

=> 해당 숫자의 방문 여부를 확인하는 리스트를 생성한 후, 이미 방문을 했으면(결과 리스트에 해당 숫자가 이미 들어있을 경우) 결과 리스트에 추가하지 않고 방문을 하지 않았다면 해당 숫자를 결과 리스트에 추가한다.

 

2. m  값이 늘어날수록 굉장히 많은 반복문이 필요하므로 재귀함수를 통해 구현을 해야 한다.

=> 재귀함수의 종료조건은 결과 리스트에 들어있는 원소의 갯수가 m자리와 같을 경우이다.

 

 

 위의 1, 2를 모두 고려한 알고리즘 설계 단계는 다음과 같다.

1. 결과값을 넣을 리스트, 방문 여부를 넣을 리스트 생성

방문 여부는 0부터 n까지 숫자가 있으므로 (n+1)만큼 False로 초기화(현재 어떤 숫자도 방문하지 않은 상태)

 

 

2. 재귀함수의 구현

2-1)  재귀함수의 종료 조건을 결과 리스트의 원소의 갯수가 m과 같을 경우로 설정

 

2-2) 반복문을 돌면서 방문한 숫자는 그냥 pass하고 방문하지 않은 숫자는 방문 여부를 True로 바꾼 후, 해당 숫자를 결과 리스트에 넣고 다시 함수를 호출

 

2-3) 다시 함수를 호출하면 다시 또 반복문을 돌면서 방문하지 않은 숫자를 결과 리스트에 넣은 후 다시 함수 호출

 

2-4)  2-3단계를 결과 리스트의 원소의 갯수가 m이 될 때까지 반복

 

2-5) 재귀함수 결과값이 반환되면 다시 결과 리스트의 맨 마지막 원소를 pop하여 빼주고 해당 숫자의 방문 여부를 False로 바꿔줌

=> 결과 리스트에 들어가는 맨 첫 번째 원소를 루트숫자라고 해보자.

루트숫자까지 pop되어도 어차피 반복문 안에 있으니 루트숫자가 다음 숫자로 이동하게 된다.

예를 들어 루트숫자가 1일 때의 모든 결과를 구해서 출력했다고 하자.

그럼 루트 숫자가 1에 대한 재귀함수가 끝이 나므로 1을 pop하고 1의 방문여부를 False로 바꿔준다.

그 다음에 반복문이 돌아가면서 2가 루트숫자가 된다. 루트숫자가 2일 때 재귀함수가 호출되면 1의 방문여부가 False이므로 1도 고려하여 결과 리스트에 넣을 수 있게 된다.

 

풀이 코드1)

def DFS():
    if len(result) == m:
        print(' '.join(map(str, result)))
        return
    else:
        for i in range(1, len(visit)):
            if visit[i] == True:
                continue
            else:
                visit[i] = True
                result.append(i)
                DFS()
                result.pop()
                visit[i] = False


n, m = map(int, input().split())
visit = [False] * (n+1)
result = []
DFS()

너무 c와 자바에 익숙해지다보니 몰랐는데 파이썬은 함수 호출시 인자를 안넣어도 돌아감..신기..

 

풀이 코드2)

풀이1과 원리는 똑같은데 방문여부를 담는 리스트를 따로 구현하지 않고 스택으로 풀이하였다.

방문 여부 리스트를 통해 결과 리스트에 중복되는 숫자가 들어가지 않도록 제어했었는데, 이를 사용하는 대신 if i in list를 활용하여 단순 조건문을 통해 해당 리스트에 중복되는 숫자가 들어가지 않게 구현하였다.

 

def DFS():
    if len(result) == m:
        print(*result)
        return
    else:
        for i in range(1, n+1):
            if i in result:
                continue
            else:
                result.append(i)
                DFS()
                result.pop()

n, m = map(int, input().split())
result = []
DFS()

 

개인적으로 재귀함수에 매우 취약하기 때문에 다시 여러 번 풀어봐야됨

 

 

풀이 코드3)

import itertools

n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]

array = itertools.permutations(nums, m) # (대상, 갯수) 조합을 구하는 함수

for i in array:
    for j in i:
        print(j, end = ' ')
    print()