[필수 알고리즘] BFS

BFS란?

- 바로가기

[필수 알고리즘] 그래프 탐색

 

풀이 방법

1. Vertex 찾기

2. 찾은 Vertex를 Queue에 저장

3. Queue에서 뽑아 반복

 

*Queue란?

- 선입선출로 먼저 들어온 것이 제일 먼저 나간다.

 

- 1번 추가 -> 2,5번 추가 -> 2번 확인하며 3번 추가 -> 5번 확인하며 4번 추가 -> 4번 확인하며 6번 추가

 

시간복잡도(Big - O)

- 알고리즘이 얼마나 오래 걸리는지

- 제한시간안에 나와야함

 

BFS의 시간복잡도

- O(V+E)로 vertex + eage이다

 

자료구조

- 검색할 그래프 : 2차원 배열

- 방문여부 확인 : 2차원 배열(재방문 금지)

- BFS실행 : Queue

 

문제 풀이

- 백준 1926

1. 

class num_1926
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
}

- " 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다"라고 해서 입력 값 두개를 받아온다

 

2.

int[][] map = new int[n][];
bool[][] chk = new bool[n][];

for (int i = 0; i < n; i++)
{
    map[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    chk[i] = new bool[m];
}

- n의 값만큼 chk에 배열을 초기화 해주고

- map에는 입력받은 값을 Split하여 값을 넣어 준다

 

3.

int cnt = 0;
int maxv = 0;

for (int j = 0; j < n; j++)
{
    for (int i = 0; i < m; i++)
    {
        if (map[j][i] == 1 && !chk[j][i])
        {
            chk[j][i] = true;
            cnt++;
        }
    }
}

- 2중 for문을 이용해 map[j][i]가 1인 값 그리고 방문하지 않은 chk[j][i]를 찾는다.

- 찾았다면 chk[j][i] 값을 방문했다는 증거로 true로 변경

- " 첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력 " 1은 그림이라는 증거이기 때문에 cnt를 +1 해준다

 

4.

static int Bfs(int y, int x, int[][] map, bool[][] chk, int n, int m)
{
    int rs = 1;
    Queue<(int, int)> q = new Queue<(int, int)>();
    q.Enqueue((y, x));
    return rs;
}

- Bfs를 위해 함수를 하나 추가 해준다.

- y,x는 이중for문의 j,i 값이다

- 결과값을 나타내느 rs와 bfs를 위한 queue를 추가한다

 

5. 

static int[] dy = { 0, 1, 0, -1 };
static int[] dx = { 1, 0, -1, 0 };

static int Bfs(int y, int x, int[][] map, bool[][] chk, int n, int m)
{
    int rs = 1;
    Queue<(int, int)> q = new Queue<(int, int)>();
    q.Enqueue((y, x));

    while (q.Count > 0)
    {
        (int ey, int ex) = q.Dequeue();

        for (int k = 0; k < 4; k++)
        {
            int ny = ey + dy[k];
            int nx = ex + dx[k];

            if (0 <= ny && ny < n && 0 <= nx && nx < m)
            {
                if (map[ny][nx] == 1 && !chk[ny][nx])
                {
                    rs++;
                    chk[ny][nx] = true;
                    q.Enqueue((ny, nx));
                }
            }
        }
    }

    return rs;
}

- while문을 이용해 q가 종료될때까지 진행하도록 만든다.

- 하나의 노드에 4방면을 검색하기 때문에 dy, dx는 그냥 외운다고 생각

- 가져온 q값을 Dequeue를 하고 4방면 체크를 위해 for문을 진행한다.

- for문을 진행하며 4방면을 돌았을때 map이 1이고 chk가 false인 값을 찾는다면 결과값 +1 하고 chk을 true로 만들어준 후 새로운 곳을 돌기 위해 q를 추가하며 반복 진행

 

*if (0 <= ny && ny < n && 0 <= nx && nx < m) 해석

- 0 <= ny - ny 값이 0 이상인지 확인 (상단 경계 체크)
- ny < n - ny 값이 n 미만인지 확인 (하단 경계 체크)
- 0 <= nx - nx 값이 0 이상인지 확인 (좌측 경계 체크)
- nx < m - nx 값이 m 미만인지 확인 (우측 경계 체크)

요약하면 n이나 m이 넘어갔는지 그리고 0보다 큰 값인지 체크

 

6. 

int cnt = 0;
int maxv = 0;

for (int j = 0; j < n; j++)
{
    for (int i = 0; i < m; i++)
    {
        if (map[j][i] == 1 && !chk[j][i])
        {
            chk[j][i] = true;
            cnt++;
            maxv = Math.Max(maxv, Bfs(j, i, map, chk, n, m));
        }
    }
}

Console.WriteLine(cnt);
Console.WriteLine(maxv);

- 만든 Bfs를 이중for문에 추가하여 그림의 넓이를 출력

 

최종코드

class num_1926
{
    static int[] dy = { 0, 1, 0, -1 };
    static int[] dx = { 1, 0, -1, 0 };

    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);

        int[][] map = new int[n][];
        bool[][] chk = new bool[n][];

        for (int i = 0; i < n; i++)
        {
            map[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            chk[i] = new bool[m];
        }

        int cnt = 0;
        int maxv = 0;

        for (int j = 0; j < n; j++)
        {
            for (int i = 0; i < m; i++)
            {
                if (map[j][i] == 1 && !chk[j][i])
                {
                    chk[j][i] = true;
                    cnt++;
                    maxv = Math.Max(maxv, Bfs(j, i, map, chk, n, m));
                }
            }
        }

        Console.WriteLine(cnt);
        Console.WriteLine(maxv);
    }

    static int Bfs(int y, int x, int[][] map, bool[][] chk, int n, int m)
    {
        int rs = 1;
        Queue<(int, int)> q = new Queue<(int, int)>();
        q.Enqueue((y, x));

        while (q.Count > 0)
        {
            (int ey, int ex) = q.Dequeue();

            for (int k = 0; k < 4; k++)
            {
                int ny = ey + dy[k];
                int nx = ex + dx[k];

                if (0 <= ny && ny < n && 0 <= nx && nx < m)
                {
                    if (map[ny][nx] == 1 && !chk[ny][nx])
                    {
                        rs++;
                        chk[ny][nx] = true;
                        q.Enqueue((ny, nx));
                    }
                }
            }
        }

        return rs;
    }
}

 

참고 영상

- 바로가기

 

문제모음

- https://www.acmicpc.net/workbook/view/18658