리그 일정짜기 단순 알고리즘 (League Scheduling)

스포츠 경기 등의 리그전에서 각 팀이 다른 모든 팀과 한 번씩 경기를 치르는 것을 라운드 로빈(round robin)이라 한다. 이 리그의 한 주기 스케쥴을 짜는 것은 여러 방법이 있지만, 아래와 같은 방법으로 단순하게 해결할 수 있다.

http://www.sciencedirect.com/science/article/pii/S0166218X04001350

위 사이트의 내용을 참고하여 GIF 애니메이션 이미지를 만들어 보았다.

1. 팀 수가 홀수일 때

각 팀이 다각형의 꼭지점에 배치되어 있다고 생각하고, 수평으로 마주보고 있는 팀과 대전한다.

한 팀은 쉰다.(쉴 수밖에 없다.)

(GIF 애니메이션입니다.)

2. 팀 수가 짝수일 때

1에서 한 팀이 쉬는 대신, 나머지 팀과 대전하면 된다.

짝수 다각형을 사용하면 된다고 생각할 수도 있지만,

그렇게 하면 꼭지점 하나를 사이에 두고 있는 팀과의 대결이 성사되지 못한다.

(GIF 애니메이션입니다.)

3.

2번은 아래와 같이 팀이 이동한다고 생각할 수도 있다.

(GIF 애니메이션입니다.)

소스코드

3번을 C++코드로 작성해 보았다.

#include <iostream>
#include <string>
#include <stdlib.h>
 
using namespace std;
 
 
int main(void)
{
    
    int *team_id;
    string team[] = { "Heros", "Eagles", "Dinos", "Lions", "Wiz",
                    "Twins", "Wyverns" ,"Tigers","Bears","Giants"};
    int numTeam = (sizeof team)/(sizeof string);
    team_id = (int*)malloc(numTeam*sizeof(int));
 
    for (int i = 0; i < numTeam; i++) {
        team_id[i] = i;
    }
 
    for (int i = 0; i < numTeam - 1; i++) {
        cout << i + 1 << "일차" << endl;
        for (int j = 0; j < numTeam/2; j++) {
            cout << team[team_id[j]] << ":" << team[team_id[numTeam-j-1]] << endl;
        }
 
        for (int j = 0; j < numTeam - 1; j++) {
            team_id[j] = (team_id[j] + 1) % (numTeam - 1);
        }
 
        cout << endl;
    }
    
    return 0;
}

출력결과

1일차
Heros:Giants
Eagles:Bears
Dinos:Tigers
Lions:Wyverns
Wiz:Twins

2일차
Eagles:Giants
Dinos:Heros
Lions:Bears
Wiz:Tigers
Twins:Wyverns

3일차
Dinos:Giants
Lions:Eagles
Wiz:Heros
Twins:Bears
Wyverns:Tigers

4일차
Lions:Giants
Wiz:Dinos
Twins:Eagles
Wyverns:Heros
Tigers:Bears

5일차
Wiz:Giants
Twins:Lions
Wyverns:Dinos
Tigers:Eagles
Bears:Heros

6일차
Twins:Giants
Wyverns:Wiz
Tigers:Lions
Bears:Dinos
Heros:Eagles

7일차
Wyverns:Giants
Tigers:Twins
Bears:Wiz
Heros:Lions
Eagles:Dinos

8일차
Tigers:Giants
Bears:Wyverns
Heros:Twins
Eagles:Wiz
Dinos:Lions

9일차
Bears:Giants
Heros:Tigers
Eagles:Wyverns
Dinos:Twins
Lions:Wiz