[Algorithm](EN) Basic DFS, BFS concept and problem

Solve basic brute force problem which use dfs and bfs.


Environment and Prerequisite

  • C++
  • Basic concept of BFS and DFS


Problem

  • Problem: There is a map like picture above. 1 represents house, 0 represents nothing. Chulsoo plans to define connected houses as apartment block and assign same number to each block. Connected houses means that specific house is connected to other houses near up, right, down and left(like on the image). Houses in cross line are not connected. Picture on the right is numbered apartment block of picture on left. Find each apartment blocks number of houses and print those houses in ascending order.


Apporach

  • We can find apartment blocks by scanning all places on the map. While searching all places on map, define apartment block when we meet 1(house) and count number of houses.
  • We need to scan all places so it is brute force search.
  • In apartment block, we need to spread out from one position to around neighbors. So we can think it as BFS or DFS.


Solution

  1. Check if there is a 1(house), while scanning all places on map.
  2. If there is a 1(house), define it as new apartment block and assign ID to it.
  3. Find number of houses in apartment block by using BFS or DFS.
  4. Add number of houses in apartment block to array.
  5. After scanning all places on map, sort array in ascending order and print it.


Definition

  • Bruete Force or Exhaustive Search: Solution which search all the possible cases.
  • It is accurate but takes long time.
  • Ex: Sum from 1 to n, Find specific number in random array


BFS and DFS

Concept

  • DFS(Depth First Search): Explores as far as possible along each branch before backtracking(move to neighbor).
  • BFS(Breadth First Search): Explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
  • See above attached image. The number is traverse order.

Method

  • DFS: Use stack or recursion
  • BFS: Use queue


Solution Codes

DFS(Recursion)

  • DFS solution using recursion
// DFS - Recursion
void dfs_recursion(int x, int y) {

    // step into function -> it means visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;

    // search around current x,y position
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        // if nx and ny are in map
        if(0 <= nx && nx < n && 0 <= ny && ny < n){
            // if cur nx,ny is not visited then -> visit
            if(map[nx][ny] == 1 && visited[nx][ny] == false){
                dfs_recursion(nx, ny);
            }
        }
    }
}

DFS(Stack)

  • DFS solution using stack
// DFS - Stack
void dfs_stack(int x, int y) {

    stack< pair<int,int> > s; // stack for dfs, (x,y) -> (row, col)
    s.push(make_pair(x,y)); // make pair data structure and push to stack

    // first visit to x,y -> make x,y position visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;

    while(!s.empty()){

        // get top element of stack
        x = s.top().first;
        y = s.top().second;
        s.pop();

        // search around current x,y position
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // if nx and ny are in map
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // if cur nx,ny is not visited then -> visit
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // increase number of houses in group_id apartment block
                    groups[group_id]++;

                    // also push current x,y and nx,ny
                    // because it is dfs(search around other positions after processing nx,ny then come back to x,y)
                    s.push(make_pair(x,y));
                    s.push(make_pair(nx,ny));
                }
            }
        }   
    }
}

BFS(Queue)

  • BFS solution using queue
// BFS
void bfs(int x, int y){

    queue< pair<int,int> > q; // queue for dfs, (x,y) -> (row, col)
    q.push(make_pair(x,y)); // make pair data structure and push to queue

    // first visit to x,y -> make x,y position visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;  

    while(!q.empty()){

        // get front element of queue
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // search around current x,y position
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // if nx and ny are in map
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // if cur nx,ny is not visited then -> visit
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // increase number of houses in group_id apartment block
                    groups[group_id]++;

                    // push current nx,ny to queue
                    q.push(make_pair(nx,ny));   
                }
            }
        }
    }
}

Full Code

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 25

using namespace std;

// up, right, down, left
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int n; // number of rows and columns
int group_id; // apartment block id, it starts from 1
int groups[MAX_SIZE * MAX_SIZE]; // number of houses in each apartment block

int map[MAX_SIZE][MAX_SIZE]; // map
bool visited[MAX_SIZE][MAX_SIZE]; // map for visited or not

// DFS - Recursion
void dfs_recursion(int x, int y) {

    // step into function -> it means visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;

    // search around current x,y position
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        // if nx and ny are in map
        if(0 <= nx && nx < n && 0 <= ny && ny < n){
            // if cur nx,ny is not visited then -> visit
            if(map[nx][ny] == 1 && visited[nx][ny] == false){
                dfs_recursion(nx, ny);
            }
        }
    }
}

// DFS - Stack
void dfs_stack(int x, int y) {

    stack< pair<int,int> > s; // stack for dfs, (x,y) -> (row, col)
    s.push(make_pair(x,y)); // make pair data structure and push to stack

    // first visit to x,y -> make x,y position visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;

    while(!s.empty()){

        // get top element of stack
        x = s.top().first;
        y = s.top().second;
        s.pop();

        // search around current x,y position
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // if nx and ny are in map
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // if cur nx,ny is not visited then -> visit
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // increase number of houses in group_id apartment block
                    groups[group_id]++;

                    // also push current x,y and nx,ny
                    // because it is dfs(search around other positions after processing nx,ny then come back to x,y)
                    s.push(make_pair(x,y));
                    s.push(make_pair(nx,ny));
                }
            }
        }   
    }
}

// BFS
void bfs(int x, int y){

    queue< pair<int,int> > q; // queue for dfs, (x,y) -> (row, col)
    q.push(make_pair(x,y)); // make pair data structure and push to queue

    // first visit to x,y -> make x,y position visited
    visited[x][y] = true;
    // increase number of houses in group_id apartment block
    groups[group_id]++;  

    while(!q.empty()){

        // get front element of queue
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // search around current x,y position
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // if nx and ny are in map
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // if cur nx,ny is not visited then -> visit
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // increase number of houses in group_id apartment block
                    groups[group_id]++;

                    // push current nx,ny to queue
                    q.push(make_pair(nx,ny));   
                }
            }
        }
    }
}

int main (){

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            // get integer one by one -> %1d
            scanf("%1d", &map[i][j]);
    }

    // search all values in map
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // if cur i,j is not visited then -> visit
            if(map[i][j]==1 && visited[i][j]==false){

                // assign id to current position(apartment block)
                group_id++;

                // Search
                //dfs_recursion(i, j);
                //dfs_stack(i, j);
                //bfs(i, j);
            }
        }
    }

    // sort number of houses in each apartment block in ascending order
    // ID starts from 1
    // usage: https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp
    sort(groups + 1, groups + group_id + 1);

    printf("%d\n", group_id);
    for (int i = 1; i <= group_id; i++) {
        printf("%d\n", groups[i]);
    }
}


Reference

Read More

[Let's Encrypt] 도메인의 인증서가 서브도메인의 인증서로 적용되었던 사례

Published on October 19, 2024

[Let's Encrypt](EN) Case of subdomain's certificate was applied to root domain

Published on October 19, 2024

[CI/CD] workflow_dispatch와 workflow_call을 사용하지 않을 때 기본값 설정하기

Published on September 16, 2024