BOJ(N과M)(1)

작성일 | In

1. 15649번 N과 M(1)

  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열 구하기

  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다

  • itertools.permutations 쓰지말고 풀어보자.

def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(result))
        return
    for i in range(1, N+1):
        # if i not in result:
        if not visited[i]:
            visited[i] = 1
            result += str(i)
            DFS(i)
            result = result[:-1]
            visited[i] = 0
N, M = map(int, input().split())
result = ""
visited = [0]*(N+1)
DFS(0)
  • 방문한 건지 확인하는 visited 배열을 따로 둘 필요 없이,
  • 주석 처리한 if i not in result:를 통해서도 판별이 가능하다.

  • 그렇지만 visited 배열을 쓸 일이 많으므로, 연습할 겸 만들었다.

  • visited 배열을 사용하지 않는다면 다음과 같다
def DFS(s):
    global result
    if len(result) == M:
        print(" ".join(result))
        return
    for i in range(1, N+1):
        if str(i) not in result:
            result += str(i)
            DFS(i)
            result = result[:-1]


N, M = map(int, input().split())
result = ""
DFS(0)
  • 20190825 ( 매개변수 사용해보기)
def DFS(s, num):
    if len(num) == M:
        print(num)
        return
    for i in range(1, N+1):
        # if i not in result:
        if not visited[i]:
            visited[i] = 1
            num += str(i)
            DFS(i, num)
            num = num[:-1]
            visited[i] = 0


N, M = map(int, input().split())
visited = [0]*(N+1)
DFS(0, "")

참고자료 [BOJ문제]https://www.acmicpc.net/problem/15649

0%