대학교 시간표 모든 경우의 수 출력기

DFS를 활용한 시간표 자동 생성기

 

시간표를 직접 짜는 것은 시간이 많이 걸리는 작업입니다. 여러 과목이 있고, 각 과목마다 가능한 시간대가 다를 때, 충돌 없이 시간표를 만드는 것은 쉽지 않습니다. 특히 대학교의 수강신청을 하기 위해 시간표를 짜는 경우에는 너무 많은 경우의 수가 존재하고 모든 경우의 수를 개인이 직접 알아내기에는 큰 어려움이 있다고 생각합니다.

이를 해결하기 위해 DFS(Depth First Search)를 활용한 자동 시간표 생성기를 만들어 보았습니다.

실제로 너무 도움이 되니 코드를 긁어 사용해보세요

1. 문제 정의

우리는 여러 과목의 가능한 시간 옵션이 주어졌을 때, 시간 충돌 없이 가능한 모든 시간표 조합을 찾고자 합니다. 각 과목은 특정 요일과 시간대에서 열리며, 같은 시간대에 두 개 이상의 수업이 겹치지 않아야 합니다.

2. 코드 설명

2.1. 입력 데이터 구조

subjects = {
    '머신러닝1': [('월',[5,6,7]),('목',[5,6,7]),('수',[6,7,8])],
    "공공데이터분석": [("월", [2, 3, 4]), ("금", [2, 3, 4])],
    "데이터베이스": [("목", [2, 3, 4]), ("금", [2, 3, 4])],
    "딥러닝응용1": [("화", [5, 6, 7])],
    "회귀분석":[("화",[2,3,4]),('목',[2,3,4])]
}

각 과목은 키(key)로, 해당 과목의 가능한 시간대는 리스트로 저장됩니다. 각 리스트의 요소는 (요일, 가능한 시간 리스트) 형태의 튜플입니다.

2.2. 시간 충돌 확인 함수

def is_conflict(schedule, new_class):
    new_day, new_times = new_class[1], new_class[2]  
    for _, day, times in schedule:
        if day == new_day and any(t in times for t in new_times):
            return True  
    return False

이 함수는 현재 선택된 시간표와 새로운 과목이 충돌하는지를 확인합니다. 동일한 요일에 시간이 겹치면 True를 반환하여 선택을 막습니다.

2.3. DFS를 활용한 백트래킹 시간표 생성

def dfs(subjects, subject_list, schedule, index, result):
    if index == len(subject_list): 
        result.append(list(schedule))
        return

    subject = subject_list[index]
    for option in subjects[subject]: 
        subject_info = (subject, option[0], option[1]) 
        if not is_conflict(schedule, subject_info):  
            schedule.append(subject_info)
            dfs(subjects, subject_list, schedule, index + 1, result)
            schedule.pop()  

DFS 알고리즘을 활용하여 가능한 모든 과목 조합을 탐색합니다. 과목을 하나씩 선택하면서, 현재 시간표와 충돌이 없으면 추가하고 다음 과목을 탐색합니다. 백트래킹을 이용하여 모든 가능한 조합을 탐색합니다.

2.4. 전체 시간표 생성 실행 함수

def generate_schedules(subjects):
    result = []
    subject_list = list(subjects.keys())  
    dfs(subjects, subject_list, [], 0, result)
    return result

이 함수는 DFS를 실행하여 최종적으로 가능한 모든 시간표 조합을 반환합니다.

2.5. 실행 및 결과 출력

schedules = generate_schedules(subjects)

for i, schedule in enumerate(schedules):
    print(f"\n시간표 {i+1}:")
    for subject, day, times in schedule:
        print(f"  - {subject}: {day} {times}")

생성된 시간표를 출력하여 확인할 수 있습니다.

3. 결과 예시

예를 들어, 위의 데이터를 실행하면 다음과 같은 시간표 조합이 출력됩니다:

시간표 1:
  - 머신러닝1: 월 [5, 6, 7]
  - 공공데이터분석: 월 [2, 3, 4]
  - 데이터베이스: 목 [2, 3, 4]
  - 딥러닝응용1: 화 [5, 6, 7]
  - 회귀분석: 목 [2, 3, 4]

시간표 2:
  - 머신러닝1: 목 [5, 6, 7]
  - 공공데이터분석: 월 [2, 3, 4]
  - 데이터베이스: 금 [2, 3, 4]
  - 딥러닝응용1: 화 [5, 6, 7]
  - 회귀분석: 화 [2, 3, 4]

(위는 일부 예제이며, 가능한 조합은 여러 개일 수 있음)

4. 마무리

DFS와 백트래킹을 활용하면 간단한 코드로 효율적인 시간표 생성을 할 수 있습니다. 이 방법을 활용하면 학교 시간표뿐만 아니라, 회의 일정 조율, 예약 시스템 등에도 응용할 수 있습니다.

 

 

아래는 원본 코드입니다. 

from itertools import product

subjects = {
    '머신러닝': [('월',[5,6,7]),('목',[5,6,7]),('수',[6,7,8])],
    "알고리즘": [("월", [2, 3, 4]), ("금", [2, 3, 4])],
    "데이터베이스": [("목", [2, 3, 4]), ("금", [2, 3, 4])],
    "딥러닝응용": [("화", [5, 6, 7])],
    "컴퓨터비전":[("화",[2,3,4]),('목',[2,3,4])]

}

def is_conflict(schedule, new_class):
    new_day, new_times = new_class[1], new_class[2]  
    for _, day, times in schedule:
        if day == new_day and any(t in times for t in new_times):
            return True  
    return False

def dfs(subjects, subject_list, schedule, index, result):
    if index == len(subject_list): 
        result.append(list(schedule))
        return

    subject = subject_list[index]
    for option in subjects[subject]: 
        subject_info = (subject, option[0], option[1]) 
        if not is_conflict(schedule, subject_info):  
            schedule.append(subject_info)
            dfs(subjects, subject_list, schedule, index + 1, result)
            schedule.pop()  

def generate_schedules(subjects):
    result = []
    subject_list = list(subjects.keys())  
    dfs(subjects, subject_list, [], 0, result)
    return result


schedules = generate_schedules(subjects)

for i, schedule in enumerate(schedules):
    print(f"\n시간표 {i+1}:")
    for subject, day, times in schedule:
        print(f"  - {subject}: {day} {times}")

subjects 에는 해당 하는 과목과 시간표를 튜플형식으로 감싸면 됩니다.