[백준 | 실버5] 5568번: 카드 놓기(백트랙킹)

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

예제 입력 1 복사

4
2
1
2
12
1

예제 출력 1 복사

7

예제 입력 2 복사

6
3
72
2
12
7
2
1

예제 출력 2 복사

68

힌트

예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.

 

풀이1

- check[i]==0을 통해서 0값만 방문하고, 방문 후 check[i]를 1로 변경하고, result에 찾은 값을 추가해다.

- 이후 DFS(L+1)로 가지 뻗어 나간 후 반복... DFS(m)까지 도달한 경우 출력하고 다시 복귀해서 check[i] == 0으로 복구

- 이렇게 풀면 중복된 수(ex : 1 2 3 1)이 나올 경우 중복된 경우까지 출력된다 흑흑ㅠㅠ

- 중복된 부분을 체크하는 방법을 찾아서 다시 풀어야겠다

import sys
sys.stdin = open("input.txt", "r")

def DFS(L) :
    global count
    if L == m :
        for i in range(m) :         #L이 m까지 도달(result[L] = a[i]으로 변경해줬던 m개 값 안에 있는거 출력)
            print(result[i], end=" ")
        count += 1
        print()
    else :
        for i in range(n) :         #n : 4, i는 0, 1, 2, 3 만큼 돌음
            if check[i] == 0 :      #체크 변수가 0인것만 본다(1로 변경한건 방문하지 않음)
                check[i] = 1        #일단 방문하면 체크 변수 변경(0->1)
                result[L] = a[i]    #result[0], result[1]에 1로 a[i] 값 추가
                DFS(L+1)            #L 증가 가지 뻗음
                check[i] = 0        #방문 완료 했으면 다시 체크 변수 변경(1->0)

n = int(input())        #n개의 숫자
m = int(input())        #m개 뽑음
a = []                  #뽑아야할 숫자 카드
result = [0] * (m + 1)
check = [0] * (n + 1)
count = 0
for i in range(n) : 
    num = int(input())
    a.append(num)
print("n : ", n, "m : ", m)
print(a)

DFS(0)
print("총개수 : ", count)

 

풀이2

 - 찾은 순열 카드를 기존에 없던 값이면 visit 리스트에 추가하여 중복문제를 제거해줬다.

 - 재귀 문제 너무 어렵다 ㅠㅠ

import sys
sys.stdin = open("input.txt", "r")

def DFS(L) :
    global count
    if L == m :
        if result not in visit: # 방문한적이 없는 경우 실행
            # for i in range(m) :         #
            #     print(result[i], end=" ")
            # print()
            visit.append(result.copy()) # copy를 쓴 이유는 배열은 포인터 개념이라 result값이 변하면 visit값 안에 들어가 있는 result 값도 변하기 때문에 배열 복사가 필요.
            count += 1  
    else :
        for i in range(n) :         #n : 4, i는 0, 1, 2, 3 만큼 돌음
            if check[i] == 0 :      #체크 변수가 0인것만 본다(1로 변경한건 방문하지 않음)
                check[i] = 1        #일단 방문하면 변경(0->1)
                result[L] = a[i]    #result[0], result[1]에 1로 a[i] 값 추가
                DFS(L+1)            #L 증가 가지 뻗음
                check[i] = 0        #방문 완료 했으면 다시 변경(1->0)

n = int(input())        #n개의 숫자
m = int(input())        #m개 뽑음
a = []                  #뽑아야할 숫자 카드
visit=[]    # 방문 기록할 변수
result = [0] * (m + 1)
check = [0] * (n + 1)
count = 0
for i in range(n) : 
    num = int(input())
    a.append(num)
# print("n : ", n, "m : ", m)
# print(a)

DFS(0)
print(count)

 

풀이3

 ※ 멘토의 풀이

#sys.stdin = open("input.txt", "r")

def test(arr, detph=[]):
    if len(detph) == m-1:
        for i in arr:
            result = "".join(detph) + str(i)
            if result in chk:
                continue
            chk.append(result)
            #print(result)
    else:
        size = len(arr)
        for index in range(size):
            test(arr[0:index]+arr[index+1:size], detph + [str(arr[index])])

n = int(input())
m = int(input())
a = []
chk = []
for i in range(n) : 
    num = int(input())
    a.append(num)

test(a, [])


print(len(chk))