태야

<내 코드>

N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# 비교값
max_ = -1e9
min_ = 1e9


def dfs(cnt, res, add, sub, mul, div):
    global max_, min_
    # 재귀 탈출 조건
    if cnt == N:
        max_ = max(res, max_)
        min_ = min(res, min_)
        return

    if add:
        dfs(cnt+1, res+nums[cnt], add-1, sub, mul, div)
    if sub:
        dfs(cnt+1, res-nums[cnt], add, sub-1, mul, div)
    if mul:
        dfs(cnt+1, res*nums[cnt], add, sub, mul-1, div)
    if div:
        dfs(cnt+1, int(res/nums[cnt]), add, sub, mul, div-1)


dfs(1, nums[0], add, sub, mul, div)
print(max_)
print(min_)

백트래킹을 이용해 모든 경우를 다 탐색하는 방법이다. 아직까지 재귀와 백트래킹 개념이 어려운 것 같다..

<내 코드>

import sys
N, M = map(int, sys.stdin.readline().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:
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            visited[i] = 1

            arr.pop()  # 탐사한 내용 제거
            # 시작 탐색 값만 제외시키도록 나머진 초기화
            for j in range(i+1, N):
                visited[j] = 0


dfs(0)

<내 코드>

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)

<내 코드>

import sys
sys.setrecursionlimit(10000) 


def dfs(x, y, cnt):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    now = (x, y)

    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = now[0] + dx[i]
        ny = now[1] + dy[i]

        if(0 <= nx < R) and (0 <= ny < C):
            if(done[strings[nx][ny]] == 0):
                done[strings[nx][ny]] = 1
                # print(done)
                dfs(nx, ny, cnt+1)
                done[strings[nx][ny]] = 0  #백트래킹


R, C = map(int, input().split())
strings = [list(map(lambda x: ord(x)-65, input())) for _ in range(R)] # 아스키 코드로 바꿔줌
done = [0]*26   # 알파벳 26개만큼 배열설정
done[strings[0][0]] = 1

ans = 1

dfs(0, 0, ans)
print(ans)

계속해서 시간 초과가 나서 실패하고, 이 코드로 겨우 통과했다. 알고리즘은 계속해서 맞았지만 재귀를 활용하다 보니 시간 초과가 많이 났다. 백트래킹의 기본 동작원리를 이해할 수 있는 문제였다.