자료구조 - 완전탐색(Brute-Force-Search) 학습_1

완전탐색 (Brute-Force-Search) 문제 1 - picnic

  • 학교에서 소풍을 가려고 한다.
  • 학생들을 두명씩 짝지어 행동하게 하려고 한다.
  • 단, 서로 친구인 경우에만 짝을 지어야 한다.
  • 서로 친구인 경우의 쌍이 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 구하는 프로그램을 구현하라.
  • n(학생 수)은 항상 짝수이다.
  • 알고리즘 문제해결 전략 1권 p.157

코드 구현 및 해설

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 학생수: n
n = 4

# 0번, 1번, 2번, 3번 학생이 있을 때, 서로 친구인 경우를 표시하기 위해 이중 리스트 사용
# 0번과 1번 친구인 경우 --> friends[0][1] = True
friends = [[False for _ in range(n)] for _ in range(n)]
# friends = [[False, False, False, False], [F, F, F, F], [F, F, F, F], [F, F, F, F]]

# 0번과 1번 친구 = 1번과 0번 친구 --> friends[0][1] = friends[1][0] = True
friends[0][1] = friends[1][0] = True
friends[1][2] = friends[2][1] = True
friends[2][3] = friends[3][2] = True
friends[3][0] = friends[0][3] = True
friends[0][2] = friends[2][0] = True
friends[1][3] = friends[3][1] = True

# 데이터 개수가 n개인 has_pair 리스트에서 특정 인덱스의 학생이 짝이 있는 경우를 True, 짝이 없는 경우를 False 로 표시
# ex. 0번과 1번 학생이 짝으로 정해진 경우, has_pair = [True, True, False, False]
has_pair = [False for _ in range(n)]

# 최초 has_pair = [False, False, False, False]
def solve(has_pair):
  # base case
  first = None
  for i in range(n):
        # has_pair에서 첫번째 False 값의 인덱스를 first 변수에 할당
        # ex. has_pair = [True, True, False, False] --> first = 2
        if has_pair[i] == False:
            first = i
            break

    # has_pair에 False 값이 없는 경우(=[True, True, True, True]), return 1
    if first == None:
        return 1

    # has_pair 에 False 가 존재하는 경우
    ret = 0
    # has_pair 에서 first 보다 큰 인덱스를 순차적으로 student 로 할당하여, 
    # 해당 인덱스의 학생이 짝이 없고 first 인덱스의 학생과 student 인덱스의 학생이 서로 친구인 경우, 짝으로 지정한다.
    # --> has_pair[student] = has_pair[first] = True 로 할당
    for student in range(first+1, n):
        if has_pair[student] == False and friends[first][student] == True:
            has_pair[student] = has_pair[first] = True
            # has_pair 인덱스 값 모두 True(=[T, T, T, T])로 설정된 경우, ret += 1
            # --> has_pair = [T, T, T, T]까지 진행된 경우를 모든 학생이 짝지어진 경우 1가지로 간주한다.
            # --> solve(has_pair) 재귀함수 호출될 때, 모든 학생이 짝지어진 경우에 first는 None이 되어 return 값으로 1을 반환한다.
            ret += solve(has_pair)
            # has_pair = [T, T, T, T]까지 진행되면 그 때의 first, student 인덱스 값에 False를 설정하여 재귀함수에 의해 has_pair에 True가 모두 채워지는 또다른 경우의 수를 찾는다.
            has_pair[student] = has_pair[first] = False

    return ret


print(solve(has_pair))
Posted