CS50 Week3: Problem Set, Tideman

하버드 CS50 강의 3주차 Problem Set 과제 Tideman 의 풀이 과정을 다룹니다.
C언어로 정렬 알고리즘을 활용하고, 이차원 배열을 통해 그래프를 표현/탐색해야 하는 문제입니다.

Intro

문제 링크에서 자세한 내용을 확인할 수 있습니다.

Ranked Pairs 선거 방식을 구현하는 문제

$ ./tideman Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Charlie

Template

이번에도 코드 템플릿이 주어져 있다.

#include <cs50.h>
#include <stdio.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i] = argv[i + 1];
    }

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // ranks[i] is voter's ith preference
        int ranks[candidate_count];

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    // TODO
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // TODO
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // TODO
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // TODO
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // TODO
    return;
}

Code

vote 함수

이전 과제와 크게 달라진 건 없다.

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i], name) == 0)
        {
            ranks[rank] = i; 
            return true;
        }
    }
    return false;
}

record_preference 함수

두개의 for loop를 사용하여 선호도를 기록한다.

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[j]]++;
        }
    }
    return;
}

add_pairs 함수

record_preference 함수 처럼 두개의 for loop를 사용하여 preference 배열을 조작한다.
j를 i + 1 부터 시작하면 같은 경우의 수를 두 번 고려하지 않아도 된다.

누가 더 선호도가 높은지를 비교하여 pairs 배열에 저장한다.

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
            // If there is a tie, skip
            else
            {
                continue;
            }
        }
    }
    return;
}

sort_pairs 함수

문제의 최대 N은 36으로 충분히 작다.
구현이 간편한 Bubble Sort나 Selection Sort를 활용해도 되겠지만, 연습 겸 강의에서 배운 Merge Sort로 구현하였다.

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    merge_sort(pairs, 0, pair_count - 1); // Pair_count - 1 -> last index of pairs[]
    return;
}

merge_sort

혼자 해보려니 생각보다 까다로워서 구글링을 많이 했다.

void merge_sort(pair pairs[], int left, int right)
{
    if (left < right)
    {   
        int mid = left + ((right - left) / 2);
        merge_sort(pairs, left, mid);
        merge_sort(pairs, mid + 1, right);
        merge(pairs, left, mid, right);
    }
}

void merge(pair pairs[], int left, int mid, int right)
{
    int left_size = mid - left + 1; 
    int right_size = right - mid; 

    pair left_arr[left_size];
    pair right_arr[right_size];

    // Copy data to temporary arrays left_arr[] and right_arr[]
    for (int i = 0; i < left_size; i++)
    {
        left_arr[i] = pairs[left + i];
    }
    for (int j = 0; j < right_size; j++)
    {
        right_arr[j] = pairs[mid + 1 + j];
    }

    int i = 0; // Initial index of left_arr[]
    int j = 0; // Initial index of right_arr[]
    int k = left; // Initial index of pairs[] subarray

    while (i < left_size && j < right_size)
    {
        // Sort in descending order
        if (strength(left_arr[i]) >= strength(right_arr[j]))
        {
            pairs[k] = left_arr[i];
            i++;
        }
        else
        {
            pairs[k] = right_arr[j];
            j++;
        }
        k++;
    }
    // Copy the remaining elements of left_arr[], right_arr[], if there are any
    while (i < left_size)
    {
        pairs[k] = left_arr[i];
        i++;
        k++;
    }
    while (j < right_size)
    {
        pairs[k] = right_arr[j];
        j++;
        k++;
    }
}

strength 함수

가독성을 위해 추가해주었다.

int strength(pair p)
{
    return preferences[p.winner][p.loser];
}

lock_pairs 함수

사이클이 생기지 않도록 순서대로 pair를 lock한다.
creates_cycle 함수를 따로 정의하여 사이클이 생기는지 확인한다.

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        if (!creates_cycle(pairs[i].winner, pairs[i].loser))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}

creates_cycle 함수

재귀적으로 구성하면 깔끔하게 구현할 수 있다.

// Check if a cycle is created when a pair is locked
bool creates_cycle(int start, int end)
{
    if (locked[end][start])
    {
        return true;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        // Check deeper paths
        if (locked[end][i] && creates_cycle(start, i)) 
        {
            return true;
        }
    }
    return false; // No cycle found
}

처음에는 11번 라인을 if (locked[end][i]) return creates_cycle(start, i)로 작성했는데,
이렇게 하니 한 쪽 방향에서 사이클이 발견되지 않으면 다른 쪽 방향을 체크하지 않고 조기 종료되는 오류가 발생했다.
메모....

print_winner 함수

// Print the winner of the election
void print_winner(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        int j = 0;
        // Check if there is a locked path to candidate i
        while (j < candidate_count && !locked[j][i]) 
        {
            j++;
        }

        // If ther is no locked path to i, i is the winner of the election
        if (j == candidate_count)
        {
            printf("%s\n",candidates[i]);
            return;
        }
    }
}