[백준] 15649번(N과 M(1))

백준 15649번

최종 제출 코드

m,n = map(int, input().split())
array = [i for i in range(1, m+1)]
cnt = 0
result=[]
visited = [False]*m

def box(arr):

  # 인수로 전달받은 리스트의 길이가 n과 일치할 경우 result에 추가 후 함수 리턴
  if len(arr) == n:
    result.append(arr)
    return
    
  # 이미 리스트에 추가된 원소들은 visited에서 True로 바꿔줌
  for i in range(len(arr)):
    index = arr[i]-1
    visited[index] = True

  # 각각의 조합을 리스트로 생성할 것이기 때문에 원본 리스트를 바꾸는게 아닌
  # 인수로 전달받은 리스트를 복사하여 사용
  ele = arr[:]
  # 전달받은 리스트를 덧붙일 수 있는 남은 원소의 개수만큼 복사하여 리스트를 만듦
  copied = [ele[:] for i in range(len(array)-len(arr))]
  # copied 리스트에 차례대로 array의 원소를 추가함
  for i in range(len(array)-len(arr)):
    j = 0
    while j<len(array):
      if visited[j] == False:
        copied[i].append(array[j])
        visited[j] = True
        break
      j+=1

  # n 깊이의 리스트 생성이 끝나면 visited 리스트를 모두 False로 세팅
  for i in range(m):
    visited[i] = False

  # copied의 모든 원소(리스트)에 대해 재귀함수 호출
  for i in range(len(copied)):
    box(copied[i])

def ordering():

  for i in range(m):
    lists = [array[i]]
    visited[i] = True
    box(lists)

ordering()

for i in range(len(result)):
  print(*result[i])

다른 사람이 작성한 코드

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()

코드 출처

◼ 스택을 활용하면 저렇게 복잡하게 코드 작성할 필요 x...

• 애초에 dfs에 대한 개념 숙지가 덜 된 듯하다...
• 리스트를 전달하고 복사해서 이용하는 것도 상당히 비효율적
• visited를 업데이트하는 방식과 빈도가 굉장히 번거롭고 너저분
• 스택을 활용하면 간단하게 해결 가능
• 재귀함수를 호출하고 호출이 끝난 뒤 마지막 원소를 pop 해주면, 하나의 조합을 완성한 뒤 이미 완성된 조합은 배제 가능(for문이 차례대로 도니까)