BFS 너비우선탐색

BFS는 탐색 방법중 하나로 시작 정점을 방문한뒤 인접한 정점들을 모두 탐색하는 방법을 뜻한다.

순차적으로 접근하는 방식을 사용하기위해 Queue 의 자료구조가 적합하며 가장 일반적이다.

 

사용시 주의할부분은 방문한곳을 다시 방문하지않게 처리해줘야한다.

 

위의 그림과 같은 노드가 있다고 가정해보자.

목적은 노드중에 8값을 찾아야한다.

 

BFS 알고리즘으로 다음과 같은 탐색을 할경우

시작점을 가장먼저 Queue에 넣음으로 시작해 인접한 모든 정점을 다시 Queue에 넣어준다.

 

Queue에 들어있던 0의 정점을 빼준뒤 인접한 정점들을 전부 확인한 다음

확인된 정점들을 다시 넣어준다.

 

 

이후 더이상 인접한 정점이 없으며 하나씩 Queue에서 빼면서 대상을 확인하면 된다.

 

 

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

풀이

int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);

int[,] arr = new int[input[0],input[1]];

for (int i = 0; i < arr.GetLength(0); i++)
{
    string input2 = Console.ReadLine();

    for (int j = 0; j < arr.GetLength(1); j++)
    {
        if(input2[j] == '1')
            arr[i,j] = int.MaxValue;
    }
}

arr[0,0] = 1;

Queue<(int,int)> q = new Queue<(int,int)>();

q.Enqueue((0,0));

while (true)
{
    if(q.Count <= 0)
        break;

    (int,int) temp = q.Dequeue();

    int x = temp.Item1;
    int y = temp.Item2;

    if(x+1 < input[0] && arr[x+1,y] > arr[x,y]+1 )
    {
        arr[x+1,y] = arr[x,y]+1;
        q.Enqueue((x+1,y));
    }

    if(x-1 >= 0 && arr[x-1,y] > arr[x,y]+1)
    {
        arr[x-1,y] = arr[x,y]+1;
        q.Enqueue((x-1,y));
    }

    if(y+1 < input[1] && arr[x,y+1] > arr[x,y]+1)
    {
        arr[x,y+1] = arr[x,y]+1;
        q.Enqueue((x,y+1));
    }
    
    if(y-1 >= 0 && arr[x,y-1] > arr[x,y]+1)
    {
        arr[x,y-1] = arr[x,y]+1;
        q.Enqueue((x,y-1));
    }
}

System.Console.WriteLine(arr[input[0]-1,input[1]-1]);

 

 

미흡한부분이나 개선될 수 있는부분이 있다면 댓글 부탁드립니다.