[백준] 15649. N과 M (1) / python 파이썬

🚩 DFS, 백트래킹, 재귀함수, 스택

 

thinking

for문을 돌면서 1부터 리스트에 넣고 M개가 다 쌓이면 출력하도록 작성함.

어차피 for문이 숫자 순서대로 돌기 때문에 수열의 순서는 굳이 고려 안함.

이미 방문했으면 건너뛰고, 방문 안했으면 방문 체크 한 후, 출력리스트에 넣고 다음 함수를 호출.

 

코드1

방문체크로 푼 풀이

def DFS():
    if len(s) == M:
        print(*s)
        return

    for i in range(1, N+1):
        if visited[i]:  # 이미 방문했으면 건너뜀
            continue

        # 방문 안했으면 방문체크 후, 출력 리스트에 넣음
        visited[i] = True
        s.append(i)
        DFS()  # 함수 다시 호출
        s.pop()  # 원상복귀 과정 필요
        visited[i] = False


        
N, M = map(int, input().split())  # N:주어진 수, M:수열의 길이
s = []  # 출력 수열 넣을 리스트 (stack)
visited = [False] * (N+1)  # 방문체크 할 리스트
DFS()

 

코드2

스택으로만 푼 풀이

def DFS():
    if len(s) == M:
        print(*s)
        return

    for i in range(1, N+1):
        if i in s:
            continue

        s.append(i)
        DFS()  # 함수 다시 호출
        s.pop()  # 원상복귀


        
N, M = map(int, input().split())
s = []  # 출력 수열 넣을 stack
DFS()

 

 

한줄후기

DFS 열공하자