[Python Algorithm] 알고스팟 소풍 - PICNIC

Chani·2021년 12월 13일
0

알고리즘

목록 보기
1/16


풀이 과정

가능한 모든 조합을 만드는 완전탐색을 이용해서 코드를 작성하였습니다.

여기서 중요한것은 중복을 피하는것인데 (0,1)과 (1,0)같이 중복된 경우가 세지면 안되기 때문에 먼저 현재 짝이 지어지지 않은 학생중 번호가 가장 작은 학생을 찾고, 그 학생의 짝을 찾는 방식으로 코드를 구현하였습니다.

번호가 가장 작은 학생을 찾을때는 초기값을 -1로 주고 짝이 지어지지않은 학생을 찾지 못하면(모든 학생이 짝을 지은 경우) 1을 리턴해주게 하였습니다.

짝을 찾는 과정은 백트래킹을 이용하여 구현하였습니다.


최종 코드

import sys
input = sys.stdin.readline

n = int(input())

def countPair():
	student = -1
	count = 0
	for i, isVisit in enumerate(visit):
		if (not isVisit):
			student = i
			break
	if (student == -1): return 1

	for i in range(student, len(visit), 1):
		if (not visit[i] and isFriend[i][student]):
			visit[i] = visit[student] = True
			count += countPair()
			visit[i] = visit[student] = False
	return count

for _ in range(n):
	studentCount, friendsPairCount = map(int, input().split())
	visit = [False] * studentCount
	isFriend = [[False] * studentCount for _ in range(studentCount)]
	friendList = list(map(int, input().split()))

	for j in range(0, len(friendList), 2):
		isFriend[friendList[j]][friendList[j+1]] = True
		isFriend[friendList[j+1]][friendList[j]] = True
	print(countPair())

결과


소풍 문제 출처
GitHub 코드

profile
프론트엔드에 스며드는 중 🌊

0개의 댓글