백준 15663 N과 M(9) 백트래킹 파이썬

15663번: N과 M (9) (acmicpc.net)

15663번: N과 M (9)

N,M시리즈를 계속 풀어 오다가 드디어 실버 2에 도달한 첫 문제였다..

앞 문제들은 다 정답률이 상당히 높았는데 이 문제부터 40퍼 대에 그쳤다. 그래서 조금 두려웠는데 시간이 더 오래 걸리긴 했지만 중요한 지점을 생각하면 정답을 도출해낼 수 있었다.

 

우선 출력 형식을 봐야 한다.

중복하는 수를 받을 수 있는데 똑같은 리스트가 나올 경우 한 번만 출력하고,

리스트 요소 개수가 2 이상일 경우에는 중복되는 값이 있으면 그 값은 도출하게 하되

중복되는 값이 없으면 이전에 나왔던 수는 제외하고 다음 수를 출력하는 형식이다.

 

이러한 특징들을 알았다면 그대로 코드로 나타내면 된다.

N,M = map(int, input().split())
tmp = list(map(int, input().split()))
tmp.sort()
lst = []
prev = 0
visited = [False] * N
def dfs(depth):
    prev = 0
    if depth == M:
        print(' '.join(map(str, lst)))
        return
    for i in range(N):
        if tmp[i] != prev and visited[i] == False:
            lst.append(tmp[i])
            prev = tmp[i]
            visited[i] = True
            dfs(depth + 1)
            lst.pop()
            visited[i] = False
dfs(0)

풀이가 조금 길긴 하지만.. 우선 dfs를 익히는 데에 중점을 두고 풀어보려고 노력했다.

나의 경우 입력으로 받은 리스트를 끝까지 참조하기는 해야되니 for문으로 N만큼 돌리면서 

1.이전에 나온 값(prev)와 같은 값이 나오는 경우는 제외

(7 9 한다음 다시 pop해서 7 다음 9를 불러오면 if문 충족 x)

2.lst에서 이미 출력된(visited[i] = true) 값이 나오는 경우는 제외

(1 1과 같은 경우 처리되지 않도록)

1,2를 만족하도록 코드를 짰다.

어떤 부분에서 어떤 조건을 넣어주는지 파악하는 것이 중요한 것 같다.