[백준] 15654 파이썬(python) : N과 M (5)

15654번 : N과 M (5)

 

 

n, m = map(int, input().split())
num = list(map(int, input().split()))
num.sort()
visit = [False] * n #1
result = []

def dfs(depth):
    if depth == m: #2
        print(*result)
    for i in range(n):
        if not visit[i]:
            result.append(num[i])
            visit[i] = True
            dfs(depth+1)
            result.pop()
            visit[i] = False
dfs(0)

 

#1 : dfs에 필요한 방문처리 자기자신을 다시 방문하지 않기위해 필요

#2 : m만큼의 깊이가 되면 출력하도록 한다.

 

1차 수정)

n, m = map(int, input().split())
answer = list(map(int, input().split()))
result = []
answer.sort()

def dfs(depth):
    if m == depth:
        print(*result)
        return
    for arr in answer: #1
        if arr in result: #2
            continue
        result.append(arr)
        dfs(depth+1)
        result.pop()
dfs(0)

 

#1 : for 문을 돌릴때 모든 경우를 다 1~n까지 찾지 않아도 되지 않을까? answer에 있는 값만 구분해주면 되지 않을까 생각이 들었다.

#2 : in 함수를 사용하면 방문기록을 작성하지 않아도 되지 않을까?

 

하지만 in 함수를 사용하면 속도가 느려진다. 모든 내용을 하나하나 확인하기 때문에 O(n)이 나올것이기 때문이다. 그래서 방문처리를 해주는 리스트 visit을 만든것 같다. 방문처리는 bfs, dfs에서도 2차원배열시 사용하니까 이왕 쓸거 같이 써두면 익숙하고 좋을것 같다.

 

2차 수정)

n, m = map(int, input().split())
answer = list(map(int, input().split()))
result = []
answer.sort()
visit = [False] * 10001 #1

def dfs(depth):
    if m == depth:
        print(*result)
        return
    for arr in answer:
        if not visit[arr]: #2
            visit[arr] = True #3
            result.append(arr)
            dfs(depth+1)
            visit[arr] = False
            result.pop()
dfs(0)

 

#1 : 방문처리를 곱하기 n을 하지 않고 10001로 하였다. 입력값의 최대값이 10000이라고 했기 때문이다.

#2 : 1~n까지 하지않고 필요한 부분만 방문확인

#3 : 백트래킹전 방문처리

 

다른풀이)

import sys
n, m = map(int, sys.stdin.readline().split())
number = list(map(int, sys.stdin.readline().split()))
res = []
number.sort()
def backTracking(depth):
    if depth == m:
        print(*res)
        return
    for i in number:
        if i not in res:
            res.append(i)
            backTracking(depth+1)
            res.pop()
backTracking(0)

 

채점 현황

 

재귀와 백트래킹은 반드시 깊이에 관해서 빠져나오도록 하는 코드가 있는데 아직 구현하는데 부족한것 같다. 더 많은 문제를 풀고 이전 문제와 비교하면서 공부해야겠다.

 

---

15649번 : N과 M (1)