Category: C++ Coding Test Tutorials

In this course, we will implement an algorithm to find paths in graphs using C++.
In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search).
During this process, we will solve problems that frequently appear in actual coding tests, and
we will explain the algorithm theory and implementation in detail.

Problem Description

You need to solve the problem of finding the shortest path between two points in a given graph.
The graph consists of nodes and edges, with each node being connected to others.
This problem is generally provided in the following format:

    Input:
    6 7
    0 1
    0 2
    1 3
    1 4
    2 5
    4 5
    3 5
    0 5

    Output:
    2
    

The first line indicates the number of nodes (vertices) and the number of edges,
while the subsequent lines represent the connection information for each edge.
The last line signifies the start and end nodes.

Algorithm Theory

Pathfinding in graphs can be performed using two methods: DFS (Depth-First Search) and BFS (Breadth-First Search).
In this course, we will focus on finding the shortest path using BFS.
BFS operates intuitively, proceeding by exploring all adjacent nodes using a queue.

Principle of BFS

The basic operating principle of BFS is as follows:

1. Add the starting node to the queue and mark it as visited.
2. Dequeue a node and explore all its adjacent nodes.
3. Add any unvisited adjacent nodes to the queue and mark them as visited.
4. Repeat steps 2 and 3 until the queue is empty.

The reason BFS guarantees the shortest path is that it processes all nodes at the same level.
By searching based on levels, the shortest path is ensured.

Problem-Solving Process

Now we will implement the algorithm necessary to solve the problem.
Below is a C++ code example for problem-solving.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int bfs(vector>& graph, int start, int end) {
    queue q;
    vector visited(graph.size(), false);
    vector distance(graph.size(), -1);
    
    q.push(start);
    visited[start] = true;
    distance[start] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
                
                if (neighbor == end) {
                    return distance[neighbor];
                }
            }
        }
    }
    return -1; // If there is no path 
}

int main() {
    int n, m;
    cin >> n >> m;
    vector> graph(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // undirected graph
    }

    int start, end;
    cin >> start >> end;

    int result = bfs(graph, start, end);
    cout << result << endl;

    return 0;
}
    

Code Explanation

The code above takes the number of nodes and edges as input,
constructs the graph based on the edge information, and then uses BFS to
find the shortest path between the starting and ending nodes.

1. First, we include the necessary header files and declare using namespace std;.
2. The bfs function takes the graph, starting node, and ending node as parameters.
3. A queue is declared, and a vector visited to indicate visitation status is initialized.
4. The starting node is added to the queue and marked as visited.
5. The process continues while the queue is not empty, dequeuing nodes and exploring adjacent nodes.
6. Unvisited adjacent nodes are added to the queue and their distance information is updated.
7. When reaching the ending node, the corresponding distance is returned.
8. The distance information is initialized to -1; when there is no path, it returns -1.

Results and Analysis

Compiling the above code and executing it with the sample input will print
the shortest path between the starting node and the ending node.
Since BFS explores all adjacent nodes, it guarantees the shortest path.
As the size of the graph increases, the search time increases proportionally, but
BFS is a suitable algorithm for most graph problems.

Complexity Analysis

The time complexity of BFS is O(V + E), where V is the number of nodes,
and E is the number of edges. The memory complexity is also O(V).
This complexity can vary depending on the structure of the graph.
In the worst case (e.g., complete graph), E can become V^2.

Conclusion

In this course, we solved the problem of finding the shortest path in a graph using C++
through the BFS algorithm. Understanding and implementing BFS is
an important aspect of coding tests, so be sure to practice thoroughly.
I hope you can build your skills through a wider variety of problems in the future.

Hello everyone! Today, we will discuss an algorithm problem related to game development in a course designed to prepare for C++ coding tests. This article will present algorithm problems necessary for game development and explain the process of solving those problems in detail. This course is intended for job seekers using C++, as well as anyone interested in game development.

Problem Description

Problem: Maze Escape

You need to find a way from the starting point (0, 0) to the destination (N-1, M-1) in a 2D maze. The maze is represented as an array of 0s and 1s, where 0 indicates a path and 1 indicates a wall. You can only move up, down, left, and right, and you need to write a program to find the minimum distance to reach the destination.

Input Format

• The first line contains two integers, N and M. (1 ≤ N, M ≤ 100)
• The next N lines contain M integers that form an array of 0s and 1s.

Output Format

• Print the minimum distance from the starting point to the destination (length of the path). Print -1 if it is not reachable.

Example Input

3 3
0 0 1
0 0 0
1 0 0

Example Output

4

Problem Solving Process

1. Problem Analysis

The given problem can be solved using either DFS (Depth First Search) or BFS (Breadth First Search) algorithms. Since we are looking for the shortest distance, it is appropriate to use BFS. BFS explores all adjacent nodes from the current position using a queue and guarantees the shortest path.

2. Algorithm Design

The BFS algorithm to be implemented follows these steps:

1. Start at the starting point (0, 0) and enqueue the position and the current distance (0).
2. Dequeue the front element from the queue and check if that position matches the destination (target).
3. If it matches, return the distance up to that point.
4. If it does not match, add all valid adjacent positions (up, down, left, right) to the queue. Valid positions are those that do not go out of bounds and are 0.
5. Search all possible paths and return -1 if the destination cannot be reached.

3. C++ Code Implementation

Now let’s implement the above algorithm in C++:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
vector<vector<int>> maze;
vector<vector<bool>> visited;

int bfs()
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visited[0][0] = true;
    int distance[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} }; // Right, Down, Left, Up
    int steps = 0;

    while (!q.empty())
    {
        int sz = q.size();
        for (int i = 0; i < sz; i++)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            // If we have reached the destination
            if (x == N - 1 && y == M - 1)
                return steps;

            for (int j = 0; j < 4; j++)
            {
                int nx = x + distance[j][0];
                int ny = y + distance[j][1];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] == 0 && !visited[nx][ny])
                {
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
        steps++;
    }

    return -1; // If it cannot be reached
}

int main()
{
    cin >> N >> M;
    maze.resize(N, vector<int>(M));
    visited.resize(N, vector<bool>(M, false));

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> maze[i][j];

    int result = bfs();
    cout << result << endl;

    return 0;
}

4. Code Explanation

The first thing set in the code is the two-dimensional vector for storing the size and contents of the maze. Then, within the BFS function, we start exploring from the starting point using a queue. At each step, we check all possible spaces to move up, down, left, and right, enqueuing them, and if we find the destination, we return the distance up to that point. Finally, in the main function, we call the implemented BFS function to output the result based on the input.

Testing and Validation

Now we will test the implemented code. We need to ensure that the results come out correctly through various test cases.

Test Cases

• Test Case 1:

          3 3
          0 0 1
          0 0 0
          1 0 0
          

  Expected Output: 4

• Test Case 2:

          3 3
          0 1 1
          0 1 0
          0 0 0
          

  Expected Output: 4

• Test Case 3:

          2 2
          1 1
          1 1
          

  Expected Output: -1 (Impossible to move)

Feedback and Continuous Improvement

This algorithm problem provides useful skills for solving various maze or pathfinding related problems in game development. It can be expanded to topics like generating more complex mazes, path optimization, or AI for enemies. Continuous practice and solving diverse problems are important to improve skills.

Conclusion

Today, we dealt with an algorithm problem related to game development as part of C++ coding tests. Through a simple example of the maze escape problem, we applied the BFS algorithm and learned how to search for the shortest path. The direction for the future is to expand to more complex problems based on these basic algorithms.

Through the content so far, I hope you have had the opportunity to build your algorithm and problem-solving skills, and also to apply those skills in game development.

In the next session, let’s delve deeper into algorithms with more diverse problems. Thank you!

Problem Description

In a city, multiple bus routes are operated, and each route circulates through designated stops.
You need to find the fastest route from stop A to stop B.
The bus departs at scheduled times, and you need to consider the time spent at each stop and the travel times.
Given the data below, write an algorithm to find the fastest bus route.

Input Format

• The first line contains the number of stops N (1 ≤ N ≤ 1000) and the number of bus routes M (1 ≤ M ≤ 10000).
• From the second line to M lines, information about each bus route is provided in the following format:
  
  Starting Stop, Ending Stop, Travel Time
• The last line contains the numbers of stop A and stop B.

Output Format

On the first line, print the shortest time (in minutes) to get from stop A to stop B.
If it is not possible to reach, print -1.

Example Input

    5 7
    1 2 10
    1 3 20
    2 3 5
    2 4 10
    3 4 10
    4 5 15
    1 5
    

Example Output

    25
    

Solution Process

To solve this problem, we need to use a shortest path algorithm.
The given graph is a weighted directed graph, so Dijkstra’s algorithm is appropriate.
Dijkstra’s algorithm is a method to find the shortest path from a single starting point to all other vertices,
and can be efficiently applied even when weights are present.

Basic Principle of Dijkstra’s Algorithm

Dijkstra’s algorithm operates on the following basic principles:

1. Set the starting vertex to initialize the shortest path to 0, and initialize other vertices to infinity.
2. Select the vertex with the shortest path among the unprocessed vertices.
3. Update the paths of adjacent vertices of the selected vertex.
4. Repeat this process until all vertices have been processed.

C++ Code Implementation

Here is a C++ code implementation based on the above algorithm.

    #include 
    #include 
    #include 
    #include 

    using namespace std;

    const int INF = numeric_limits::max();

    void dijkstra(int start, int n, vector>>> &graph, vector &dist) {
        priority_queue, vector>, greater>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (auto &neighbor : graph[u]) {
                int v = neighbor.first;
                int weight = neighbor.second;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    int main() {
        int N, M;
        cin >> N >> M;
        vector>> graph(N + 1); // N stops

        for (int i = 0; i < M; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
        }

        int A, B;
        cin >> A >> B;

        vector dist(N + 1, INF);
        dijkstra(A, N, graph, dist);

        if (dist[B] == INF) {
            cout << -1 << endl;
        } else {
            cout << dist[B] << endl;
        }

        return 0;
    }
    

Code Explanation

The above code implements a method to find the shortest path from the given stop using Dijkstra’s algorithm.
The main steps are as follows:

1. Store the graph in the adjacency list format based on the given input.
2. Call the Dijkstra function to find the shortest path from the starting stop to other stops.
3. As a result, if the shortest path to the destination stop is infinity, it means it cannot be reached, so print -1;
   otherwise, print the time taken for the shortest path.

Conclusion

In this lecture, we addressed the problem of finding the shortest path between the starting point and destination in a graph with multiple bus routes and stops.
We learned the concept of finding the shortest path using Dijkstra’s algorithm and how to implement it.
Based on this, we have laid the foundation to solve other similar problems.