종만북 6-3 소풍 파이썬

6-4 풀이 : 소풍

 

완전 탐색

이렇게 가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 조합을 모두 만들어 보는 것 입닏. 재귀 호출을 이용해 코드를 작성해 봅시다.

재귀 호출을 이용해 문제를 해결하려면, 우선 각 답을 만드는 과정을 여러 개의 조각으로 나눠야합니다.여기서는 전체 문제를 n/2 개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 준다. 이때 문제의 형태를 ' 아직 짝을 찾지 못한 학생들의 명단이 주어질때, 친구끼리 둘 씩 짝짓는 경우릐 수를 계산하라. ' 가 됩니다. 명단에서 서로 친구인 두 학생을 찾아, 이들을 짝지어 주고나면 남은 학생들을 짝지어주는 문제도 원래 문제와 같은 형태가 된다.

각 단계에서 가장 번호가 빠른 학생의 짝을 찾아 반복을 제거함.

 

 

---

내가 푼 풀이

# 풀이 1 : 재귀
def fire( start_node, people, visitied,n, friend_ship):
    if   len(visitied) == n//2:
        print(visitied)
        global answer
        answer+=1
        return 
    else:
        while start_node<len(friend_ship)-1:
            start_node +=1
            if (friend_ship[start_node][0]  in people) and ( friend_ship[start_node][1]  in people): 
                people2 = people[:]
                people2.remove(friend_ship[start_node][0])
                people2.remove(friend_ship[start_node][1])
                visitied2 = visitied[:]

                visitied2.append(friend_ship[start_node])
                fire( start_node, people2, visitied2,n, friend_ship)
        return 





answer=0
c   = 1
for _ in range(1):
    n, m  = map(int, "6 10".split(" "))
    friend_ship_input=list(map(int,"0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5".split(" ")))
    friend_ship_input
    friend_ship=[]
    for i in range(len(friend_ship_input)//2):
        friend_ship.append([friend_ship_input[2*i+1],friend_ship_input[2*i]])
    people = list(range(n))
    global answer
    answer=0
    for i in range(len(friend_ship)):
        people3 = people[:]
        people3.remove(friend_ship [i][0])
        people3.remove(friend_ship[i][1])
        # 반복문으로 friend_ship 에서  이미 줄선 애들 뺴는 것도 좋은 생각

        fire(i, people3, [friend_ship[i]],n, friend_ship)
    print(answer)

# 풀이 2: 조합 cmbinations
import itertools
n, m  = map(int, "6 10".split(" "))
friend_ship_input=list(map(int,"0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5".split(" ")))
friend_ship_input
friend_ship=[]
for i in range(len(friend_ship_input)//2):
    friend_ship.append([friend_ship_input[2*i+1],friend_ship_input[2*i]])
people = list(range(n))
#print(friend_ship)
peopleHalf = n//2
people_combi = list(itertools.combinations(friend_ship,3))
#print(people_combi)
answer=0
for i in people_combi:
    ff=set()
    ff.add(i[0][0])
    ff.add(i[0][1])
    ff.add(i[1][0])
    ff.add(i[1][1])
    ff.add(i[2][0])
    ff.add(i[2][1])
    if len(ff) == n:
        answer+=1
print(answer)

 

---

이런식으로 완전 탐색이 가능하구나..

 

 

 

int n;
bool areFriends[10][10];// taken[i] = i 번째 학생이 짝을 이미 찾았으면, true 아니면 false

int countParsing(bool taken[10]){
	// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
    int firstFree = -1;
    for( int i =0; i<n ; ++i){
        if(!taken[i]){
            firstFree =i;
            break;
        }
    }
	// 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
	if(firstFree == -1) return 1;
	int ret =0;
	// 이 학생과 짝을 지을 학생을 결정한다.
    for( int pairWith = firstFree +1; pairWith <n ; ++pairWith){
            if (!taken[pairWith] && areFriends[firstFree][pairWith]){
                    taken[firstFree] = taken[pairWith] = true;
                    ret+=countPairings(taken);
                    taken[firstFree] =taken[pairWith] = false;
                  }
      }
   	return ret;

}