백준 15649 - 파이썬

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

15649번: N과 M (1)

문제 풀이

백트래킹을 이용하여 푸는 문제이다. 두 자리수만 출력하는 경우에는 이중 반복문을 통해 해당 값을 리스트에 저장 후 출력하는 경우까지는 생각하여 풀었지만, 길이가 m인 경우를 어떻게 백트래킹으로 구현하면 될지 몰라 다른 사람의 풀이를 찾아 보았다. 

 

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

s = [] # 출력할 숫자 저장할 리스트

def dfs():
  if len(s) == m: # m의 길이와 일치하면 출력
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i not in s: # s리스트 안에 없는 숫자는 추가
      s.append(i)
      dfs() # 없는 숫자 저장 후 다시 함수 재호출
      s.pop() # 호출이 모두 완료된 후 함수가 종료되면서 s에 있는 값 전부 pop

dfs()

 

아직 백트래킹에 대한 두번째 문제이기 때문에 대충 어떻게 풀면 되겠다는 감만 잡고, 내 생각이 맞는지 바로 다른 사람의 풀이를 보며 확인했다. 방향성에 대해서는 일치했기에 실력이 조금 늘었다 볼 수 있을거 같다. 그래도 아직 직접 백트래킹을 적용하여 풀기에는 역부족이니 좀 더 노력해야 되겠다.