[백준/python] 15665 - N과 M (11)

문제: https://www.acmicpc.net/problem/15665

 

 

사용 알고리즘: DFS 깊이우선탐색, 재귀

 

 

이 문제를 읽었을 때 바로 DFS 가 떠올랐다. 우선 내려갈 수 있을만큼 내려갔다가 방문할 수 있는 곳을 방문하면서 출력하면 되겠다고 생각했다. 

 

 

구현로직

 

1. M 개의 수열 -> 몇 개가 될지 모름 -> 재귀를 이용해 타고 내려가기

2. 재귀가 끝나야 할 조건

-> M 개의 수열이라고 했으니, 방문한 노드가 M 개가 되면 리턴

3. 재귀를 마치고 재귀함수가 호출됐던 곳으로 돌아왔다면 방문할 수 있는 노드를 모두 방문한 것이므로 pop 으로 큐에서 제거

4. for 문을 돌면서 다시 방문할 노드 탐색

 

import sys
from collections import deque

# 입력
N, M = map(int, sys.stdin.readline().split())
# set -> 중복제거
nums = sorted(set(map(int, sys.stdin.readline().split())))

# 방문노드를 저장할 큐
q = deque()

def dfs():
	# 큐의 길이가 M이면 출력하고 리턴
    if len(q) == M:
        print(*q)
        return
        
    for i in range(len(nums)):
        # 방문한 노드가 아닐 때 -> 방문노드 업데이트
        q.append(nums[i])
        # 재귀를 이용해 타고 내려감
        dfs()
        # 리턴돼서 돌아왔을 때 pop
        q.pop()

dfs()

 

 

참고

 

* unpacking operation

a = [1, 2, 3]

print(*a)

# 출력: 1 2 3

a = [1, 2, 3]

print(*a, sep='/n')

'''
출력
1
2
3
'''

a, *b = [1, 2, 3]

print(a)
print(*b)

# 출력: 1
# 출력: 2 3