태야

<내 코드>

N, M = map(int, input().split())
#visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        arr.append(i+1)
        dfs(cnt+1)  # 다음 깊이 탐색
        arr.pop()  # 탐사한 내용 제거


dfs(0)

앞의 (1), (2) 순열, 조합 문제랑은 다르게 같은 수 중복 제거가 없다. 중복이 허용되고 그냥 탐사한 내용만 제거해주면 간단하게 된다.

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []

def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            arr.pop()  # 탐사한 내용 제거

            # 순열 부분과의 차이점
            for j in range(i+1, N):
                visited[j] = 0

dfs(0)

처음 i의 DFS 탐색에 사용 된 i값을 제외시키는 것이 순열과 다른 조합의 차이다.

파이썬 itertools 모듈의 combinations를 사용한 방법

from itertools import combinations

N, M = map(int, input().split())

p = combinations(range(1, N+1), M)
for i in p:
    print(*i)

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색

            visited[i] = 0  # 탐사 완료 후 다시 초기화
            arr.pop()  # 탐사한 내용 제거


dfs(0)

DFS와 백트래킹을 이용해 푸는 문제다. 재귀가 사용되다 보니 이해를 하는데 꽤 힘들었다.. 

파이썬 itertools 모듈을 사용한 방법

from itertools import permutations

N, M = map(int, input().split())

p = permutations(range(1, N+1), M)
for i in p:
    print(*i)

<내 코드>

from collections import deque


def bfs():

    while q:
        s, c = q.popleft()
        # 복사, 붙여넣기, 삭제 후 1초씩 증가 && 다녀간 곳 q에 추가
        # 복사
        if check[s][s] == -1:
            check[s][s] = check[s][c] + 1
            q.append((s, s))
        # 붙여넣기
        if s+c <= S and check[s+c][c] == -1:
            check[s+c][c] = check[s][c] + 1
            q.append((s+c, c))
        # 삭제
        if s-1 >= 0 and check[s-1][c] == -1:
            check[s-1][c] = check[s][c] + 1
            q.append((s-1, c))


S = int(input())
q = deque()
MAX = 1001
check = [[-1]*MAX for _ in range(MAX)]

check[1][0] = 0
q.append((1, 0))

bfs()

ans = -1
for i in range(S):
    if check[S][i] != -1:
        if ans == -1 or ans > check[S][i]:
            ans = check[S][i]
print(ans)

처음에 문제를 복사 - 붙여 넣기 - 복사- 붙여 넣기... 하는 것으로 잘못 이해했었다. 실제로는 클립보드에 들어있는 이모티콘은 여러 번 화면에 붙여 넣기가 가능한 것이다.

이 문제는 기존의 BFS 문제랑 조금 차이가 있다. 기존에는 입력을 그래프 형태로 주어졌는데, 이 문제는 본인이 새로 그래프를 만들어야 했다. 복사, 붙여넣기, 삭제 부분을 작성하고 현재 s,c에 대한  시간 check [s][c] 값에 +1초씩 해준다.  그리고 찾고자 하는 입력 값 check [s] 중 최솟값을 찾아 출력하면 된다.