Chapter 4-4. 그래프 순회 방법 2️⃣ - BFS(너비 우선 탐색)

Date: 2020.10.06 Updated: 2020.10.06

카테고리: Algorithm Lesson 2

태그: BFS C Sharp Data Structure Algorithm

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 4. 그래프

🚖 BFS

가까운 순서대로 방문한다.

출발 정점을 기준으로 가까운 순서대로 차례 차례 방문함.
예를 들어 순회을 0 정점에서 시작한다면
- 0 정점에서 거리 1 (간선 1 개를 타야 갈 수 있는) 👉 1, 3
- 0 정점에서 거리 2 (간선 2 개를 타야 갈 수 있는) 👉 2, 4
- 0 정점에서 거리 3 (간선 3 개를 타야 갈 수 있는) 👉 5
- 최종적으로 BFS 순회는 0 1 3 2 4 5 순으로 방문하게 된다.

Queue 큐로 구현한다.

그 때, 그 때 방문하는 정점마다 가장 가까운 거리의 정점들을 큐에 넣는다.
선입선출. 즉, 들어간지 오래된 정점부터 빠져나오게 된다.
DFS 👉 다양한 용도에 사용 됨
BFS 👉 거의 한 가지 용도로만 사용 된다! ⭐최단 거리 길 찾기⭐>

BFS 코드

using System;
using System.Collections.Generic;

namespace Excercise
{
    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { 0, 1, 0, 1, 0, 0 },
            { 1, 0, 1, 1, 0, 0 },
            { 0, 1, 0, 0, 0, 0 },
            { 1, 1, 0, 0, 1, 0 },
            { 0, 0, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0 },
        };

        public void BFS(int start)
        {
            bool[] found = new bool[6];  // false로 초기화 되어 있음

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while (q.Count > 0)
            {
                // 1. 방문
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 2. 나와 가까운 정점들 중 방문하지 않은 애가 있다면 큐에 추가하여 예약
                for (int next = 0; next < 6; next++)
                {
                    if (adj[now, next] == 0)  // 연결 되어 있지 않으면 스킵
                        continue;
                    if (found[next])  // 이미 방문한 애라면 스킵
                        continue;
                    
                    // 예약
                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.BFS(0);  // 0 1 3 2 4 5
        }
    }
}

큐에 다음에 방문할 정점들을 추가한다. 즉, 다음에 방문할 정점들을 순서대로 예약하는 것.

아래 과정을 반복한다.
- 1️⃣ 방문 int now = q.Dequeue();
  - now 예약 큐에서 들어간지 가장 오래된 정점을 꺼내온다.
- 2️⃣ 현재 방문하고 있는 정점 now가 앞으로 방문할 수 있는 정점들을 큐에 넣어 예약하기
  - 모든 정점들을 검사한다. (next)
    - now와 연결 되어 있는 곳이고 and 아직 방문하지 않는 정점이라면
      - 해당 정점 next를 다음에 방문할 수 있도록 큐에 넣어 예약한다.
      - found 로 한번이라도 예약된 적이 있다는 것을 체크하기
출발지를 기점으로 거리 순서대로 가까운 정점들을 차례대로 방문하게 된다.
graph.BFS(0) 👉 0 1 3 2 4 5 순으로 방문

BFS 순회한 노드들로부터 부모, 거리 정보 얻기

using System;
using System.Collections.Generic;

namespace Excercise
{
    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { 0, 1, 0, 1, 0, 0 },
            { 1, 0, 1, 1, 0, 0 },
            { 0, 1, 0, 0, 0, 0 },
            { 1, 1, 0, 0, 1, 0 },
            { 0, 0, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0 },
        };

        public void BFS(int start)
        {
            bool[] found = new bool[6];  // 한번이라도 예약된적이 있는지 여부
            int[] parent = new int[6];  // 내 부모가 누구인지
            int[] distance = new int[6]; // 내가 오기까지 얼마의 거리가 걸렸는지

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;
            parent[start] = start;  // 출발지는 자기 자신이 부모라고 하자.
            distance[start] = 0;

            while (q.Count > 0)
            {
                // 1. 방문
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 2. 나와 가까운 정점들 중 방문하지 않은 애가 있다면 큐에 추가하여 예약
                for (int next = 0; next < 6; next++)
                {
                    if (adj[now, next] == 0)  // 연결 되어 있지 않으면 스킵
                        continue;
                    if (found[next])  // 이미 한번이라도 예약된적이 있는 애라면 스킵
                        continue;
                    
                    // 예약
                    q.Enqueue(next);
                    found[next] = true;
                    parent[next] = now;
                    distance[next] = distance[now] + 1;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.BFS(0);  // 0 1 3 2 4 5
        }
    }
}

found 👉 한번이라도 예약된적이 있는지
parent 👉 해당 인덱스에 대응하는 정점의 부모가 누구인지
distance 👉 출발지로부터 해당 인덱스에 대응하는 정점까지의 거리

// 예약
q.Enqueue(next);
found[next] = true;
parent[next] = now;
distance[next] = distance[now] + 1;

방문할 수 있는 정점 next 을 큐에 예약할 때 parent, distance도 함게 업뎃
- next의 부모는 now (now로부터 연결 정점을 찾은 것이므로)
- start로부터 next까지의 거리는 now까지의 거리인 distance[now]에서 1 더한다.
parent 👉 0 0 1 0 3 4
- 0 정점 부모 - 0
- 1 정점 부모 - 0
- 2 정점 부모 - 1
- 3 정점 부모 - 0
- 4 정점 부모 - 3
- 5 정점 부모 - 4
distance 👉 0 1 2 1 2 3
- 거리 0 - 출발지인 정점 0
- 거리 1 - 정점 1, 정점 3
- 거리 2 - 정점 2, 정점 4
- 거리 3 - 정점 5

이처럼 BFS를 통해 해당 정점까지의 최단 거리를 정보를 담을 수 있다. 👉 최단 거리 길 찾기에 사용 됨.

🚖 BFS 를 사용한 미로 길 찾기

BFS 는 거의 한 가지 용도로만 사용 된다! ⭐최단 거리 길 찾기⭐>

미로의 타일 또한 그래프로 나타낼 수 있다. 타일 하나 하나를 정점(Vertex)으로 보고, 현재 타일로부터 해당 타일이 갈 수 있는 타일이라면 연결(Edge) 되는 것으로 표현할 수 있고, 갈 수 없는 벽이라면 연결이 되어 있지 않은 관계라고 생각해볼 수 있다.

📜Player.cs - BFS

        public void Initialize(int posY, int posX, Board board)
        {
            PosX = posX;
            PosY = posY;
            _board = board;

            BFS();
        }

        void BFS()
        {
            int[] deltaY = new int[] { -1, 0, 1, 0 };
            int[] deltaX = new int[] { 0, -1, 0, 1 };

            bool[,] found = new bool[_board.Size, _board.Size];
            Pos[,] parent = new Pos[_board.Size, _board.Size];

            Queue<Pos> q = new Queue<Pos>();
            
            q.Enqueue(new Pos(PosY, PosX));  // 시작점
            found[PosY, PosX] = true;
            parent[PosY, PosX] = new Pos(PosY, PosX);

            while(q.Count > 0)
            {
                Pos pos = q.Dequeue();
                int nowY = pos.Y;
                int nowX = pos.X;

                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + deltaY[i];
                    int nextX = nowX + deltaX[i];

                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;
                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;
                    if (found[nextY, nextX])
                        continue;

                    q.Enqueue(new Pos(nextY, nextX));
                    found[nextY, nextX] = true;
                    parent[nextY, nextX] = new Pos(nowY, nowX);
                }
            } 

            int y = _board.DestY;
            int x = _board.DestX;
            while (parent[y, x].Y != y || parent[y, x].X != x)
            {
                _points.Add(new Pos(y, x));
                Pos pos = parent[y, x];
                y = pos.Y;
                x = pos.X;
            }
            _points.Add(new Pos(y, x));
            _points.Reverse();
        }

오른 손 법칙에서 그랬던 것과 마찬가지로 *Update 함수에서 플레이어의 위치를 프레임마다 결정하지 않고 미리 플레이어 위치 초기화 과정에서 미리 도착지까지 향하는 길(플레이어 위치들)을 결정해두고 리스트에 저장해둔다. Update 함수에서는 리스트에 있는 타일들을 꺼내면 될 뿐.*

deltaY, deltaX
- 반시계 방향으로 Up, Left, Down, Right 순으로
  - Up 방향으로 가기 위해선 Y 방향으로 deltaY[0](-1) 만큼, X 방향으로 deltaX[0](0) 만큼 이동하면 된다.
  - Left 방향으로 가기 위해선 Y 방향으로 deltaY[1](0) 만큼, X 방향으로 deltaX[1](-1) 만큼 이동하면 된다.
  - Down 방향으로 가기 위해선 Y 방향으로 deltaY[2](1) 만큼, X 방향으로 deltaX[2](0) 만큼 이동하면 된다.
  - Right 방향으로 가기 위해선 Y 방향으로 deltaY[3](0) 만큼, X 방향으로 deltaX[3](1) 만큼 이동하면 된다.
found 👉 한번이라도 예약된적이 있는 타일 체크
parent 👉 해당 타일의 부모 (연결된 이전 노드)
q 👉 추후 방문할 정점들을 큐에 추가하여 예약. 자신의 가까운 정점들을 차례로 추가한다.
시작하기
- q 큐에 시작 위치(인수로 들어온 PosX, PosY) 넣기
- found 일단 시작 위치는 방문 처리 true
- parent 시작 위치의 부모는 자기 자신
큐가 빌 때까지, 즉 더 이상 예약 된 정점이 아무 것도 없을 때 까지 아래 과정을 반복한다.
- 1️⃣ 큐에서 꺼내기 (현재 방문 중) 👉 nowY, nowX
- 2️⃣ 다음에 방문할 수 있도록 큐에 예약하기
  - 현재 방문 중인 nowY, nowX을 기준으로 4 개의 방향 Up, Left, Dowwn, Right 검사 (nextY, nextX) 👉 본인 기준 가장 가까운 정점을 검사하는 것과 같다. 본인 주변 4 방향 타일을 검사하는 것이니까.
    - 런타임 에러 방지(인덱스 벗어나진 않는지 검사)
    - 1️⃣ nextY, nextX가 갈 수 있는 곳인지 (벽인지) 검사
      - 그래프로 따지면 연결 되지 않은 곳인지를 검사
    - 2️⃣ nextY, nextX가 방문 했던 곳인지 검사
  - 검사 통과 되었으면 방문 가능한 정점이므로 큐에 추가하여 예약하자.
    - 큐에 nextY, nextX 추가
    - nextY, nextX 미리 방문 체크
    - nextY, nextX의 부모(연결된 이전 정점)는 nowY, nowX
여기까지 완료 하면 parent에 벽이 아닌 모든 타일들에 자신의 이전 정점 정보가 들어간다.
- 목적지를 시작으로 목적지부터 거꾸로 부모를 타고 타고 올라가며 그 길을 리스트에 저장하자. 시작점에 도달할 때까지 👉 최단 경로
  - 그 때 그 때 정점을 받문할 때마다 자신과 가장 가까운, 즉 바로 4 방향중에 하나로 연결된 정점들을 우선적으로 순서대로 방문하기 때문에 ⭐어떤 정점이던 간에 부모를 타고 타고 올라가면 출발지까지 최단 경로로 올라갈 수 있다는게 보장된다.⭐
    - BFS 언제나 가까운 거리 순으로 방문했으므로 예를 들어 지금 정점5를 방문 중이라면 출발지부터 정점5까지 갈 수 있는 길 중 최단 거리다.
- 시작점은 부모가 자기 자신과 같으므로 부모와 자기 자신이 같을 때까지 반복하면 된다. 그게 바로 시작점에 도착한 것.
마지막으로 리스트를 Reverse 뒤집어 주면 출발지 부터 목적지까지의 최단 경로 타일들이 저장된 리스트가 되는 것이다.
- 마지막으로 _points.Add(new Pos(y, x)); 한번 더 추가해준 이유는 출발지 정점은 while 조건문에 위배되서 while문을 못 돌아서 리스트에 추가가 안되기 때문.
리스트를 순서대로 쭉 돌며 플레이어 위치를 업뎃해나가면 그게 바로 최단 경로.

📜Player.cs - 전체 코드

namespace Algorithm
{
    class Pos
    {
        public Pos(int y, int x) { Y = y; X = x; }
        public int Y;
        public int X;
    }

    class Player
    {
        public int PosY { get; private set; }
        public int PosX { get; private set; }

        Random _random = new Random();

        Board _board;

        enum Dir  // 반시계방향
        {
            Up = 0,
            Left = 1,
            Down = 2,
            Right = 3
        }

        int _dir = (int)Dir.Up;

        List<Pos> _points = new List<Pos>();

        public void Initialize(int posY, int posX, Board board)
        {
            PosX = posX;
            PosY = posY;
            _board = board;

            BFS();
        }

        void BFS()
        {
            int[] deltaY = new int[] { -1, 0, 1, 0 };
            int[] deltaX = new int[] { 0, -1, 0, 1 };

            bool[,] found = new bool[_board.Size, _board.Size];
            Pos[,] parent = new Pos[_board.Size, _board.Size];

            Queue<Pos> q = new Queue<Pos>();
            q.Enqueue(new Pos(PosY, PosX));  // 시작점
            found[PosY, PosX] = true;
            parent[PosY, PosX] = new Pos(PosY, PosX);

            while(q.Count > 0)
            {
                Pos pos = q.Dequeue();
                int nowY = pos.Y;
                int nowX = pos.X;

                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + deltaY[i];
                    int nextX = nowX + deltaX[i];

                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;
                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;
                    if (found[nextY, nextX])
                        continue;

                    q.Enqueue(new Pos(nextY, nextX));
                    found[nextY, nextX] = true;
                    parent[nextY, nextX] = new Pos(nowY, nowX);
                }
            } 

            int y = _board.DestY;
            int x = _board.DestX;
            while (parent[y, x].Y != y || parent[y, x].X != x)
            {
                _points.Add(new Pos(y, x));
                Pos pos = parent[y, x];
                y = pos.Y;
                x = pos.X;
            }
            _points.Add(new Pos(y, x));
            _points.Reverse();
        }

        void RightHand()
        {
            // 현재 바라보고 있는 방향을 기존으로 좌표 변화를 나타냄
            int[] frontY = new int[] { -1, 0, 1, 0 };
            int[] frontX = new int[] { 0, -1, 0, 1 };
            int[] rightY = new int[] { 0, -1, 0, 1 };
            int[] rightX = new int[] { 1, 0, -1, 0 };

            _points.Add(new Pos(PosY, PosX));

            // 목적지 도착하기 전에는 계속 실행
            // 실시간으로 로직 돌리기 전에, 렌더링도 하기 전에, 미리 길을 찾아 보는 것이다.
            // 현재 바라보는 방향이 어디냐에 따라 오른손 위치가 다름.(왼쪽을 보고 있는 상태라면 오른손은 절대 기준으로 위쪽일것)
            while (PosY != _board.DestY || PosX != _board.DestX)
            {
                // 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인
                if (_board.Tile[PosY + rightY[_dir], PosX + rightX[_dir]] == Board.TileType.Empty)
                {
                    // 오른쪽으로 가기
                    // 1. 오른쪽 방향으로 90 도 회전
                    _dir = (_dir - 1 + 4) % 4;
                    // 2. 앞으로 한 보 전진
                    PosY = PosY + frontY[_dir];
                    PosX = PosX + frontX[_dir];

                    _points.Add(new Pos(PosY, PosX));
                }
                // 2. 현재 바라보는 방향을 기준으로 앞 쪽으로 갈 수 있는지
                else if (_board.Tile[PosY + frontY[_dir], PosX + frontX[_dir]] == Board.TileType.Empty)
                {
                    // 앞으로 한 보 전진
                    PosY = PosY + frontY[_dir];
                    PosX = PosX + frontX[_dir];

                    _points.Add(new Pos(PosY, PosX));
                }
                else
                {
                    // 왼쪽 방향으로 90 도 회전 해주고 다음 반복 하러 (반시계방향으로 여러 방향 따져봄) 
                    _dir = (_dir + 1 + 4) % 4;
                }
            }
        }

        const int MOVE_TICK = 10;   // 10밀리세컨즈 = 0.01 초 마다 움직이게
        int _sumTick = 0;
        int _lastIndex = 0;
        public void Update(int deltaTick)
        {
            if (_lastIndex >= _points.Count)
                return;

            _sumTick += deltaTick;
            if (_sumTick >= MOVE_TICK)  // 이부분은 0.1초마다 실행
            {
                _sumTick = 0;

                PosY = _points[_lastIndex].Y;
                PosX = _points[_lastIndex].X;
                _lastIndex++;
            }
        }
    }
}

🚖 BFS 단점

BFS 는 모든 경로를 동일한 조건으로 이동할 수 있을 때만 사용이 가능하다. 가중치 있는 그래프에선 X

제한적인 상황에서만 사용이 가능
- 가중치가 없이 모든 정점이 동등한 경우에만 사용 가능
- 만약 상하좌우 뿐만이 아니라 대각선 이동도 가능하여 총 8 개의 방향으로 움직일 수 있다면 (즉, 연결되어 있는 정점이 8개라면)
  - 상하좌우 이동 비용이 1 이라면
  - 대각선 이동 비용은 \(sqrt(2)\) 이기 때문에 대각선과 상하좌우 정점들이 서로 동등하지 못하다.
    - BFS는 자신과 연결되어 있는 정점들을 모두 차례대로 동등하게 탐색하는데, 가중치가 다르므로 거리에 있어 모호해지기 때문이다.

가중치 있는 그래프는 다익스트아 최단 경로 알고리즘 에서 순회

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Twitter Facebook LinkedIn

👱‍♀️ ansohxxn

Chapter 4-4. 그래프 순회 방법 2️⃣ - BFS(너비 우선 탐색)

Chapter 4. 그래프

🚖 BFS

BFS 코드

BFS 순회한 노드들로부터 부모, 거리 정보 얻기

🚖 BFS 를 사용한 미로 길 찾기

📜Player.cs - BFS

📜Player.cs - 전체 코드

🚖 BFS 단점

공유하기

댓글남기기

참고

2020.10.25
[고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24
(C++) 동적 계획법 Dynamic Programming

2020.10.24
[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

👱‍♀️ ansohxxn

Chapter 4. 그래프

🚖 BFS

BFS 코드

BFS 순회한 노드들로부터 부모, 거리 정보 얻기

🚖 BFS 를 사용한 미로 길 찾기

📜Player.cs - BFS

📜Player.cs - 전체 코드

🚖 BFS 단점

공유하기

댓글남기기

참고

2020.10.25 [고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25 [고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24 (C++) 동적 계획법 Dynamic Programming

2020.10.24 [고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24
(C++) 동적 계획법 Dynamic Programming

2020.10.24
[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐