문제

최단 거리 찾기 == BFS 알고리즘

이라고 생각하면 된다.

BFS 알고리즘

• 루트 노드에서 인접한 노드를 탐색하여 순회하는 방법이다.
• Queue를 이용하여 구현하는 것이 일반적이다.
• Queue가 모두 소진될 때까지 루프하여 인접노드들을 검색한다.

순서

1. 지도를 2차원 배열로 표현한다.
2. 출발점을 큐에 넣고 방문을 표시한다.
3. 큐에서 노드를 하나씩 꺼내면서 상하좌우로 이동 가능한 지점을 찾습니다.
4. 이동 가능한 지점을 큐에 추가하고 방문 표시를 합니다.
5. 도착점에 도달하면 경로를 찾은 것이므로 종료한다.

이동 가능한 노드가 없다면 4번 로직이 실행되지 않고 큐가 모두 소진될 것이다.
또한 2번의 방문 표시를 하기 위해 지도와 같은 2차원 배열이 하나 더 필요하다.

델타 값

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

이 코드에서 dx 와 dy 배열은 각각 상하좌우로 이동하는 델타 값을 의마한다.
현재 위치에서 dx[i]와 dy[i] 값을 더함으로서 상하좌우 이동한 위치를 계산할 수 있다.
이렇게 계산된 새로운 위치가 유효하고, 이동 가능하며 아직 방문하지 않은 곳이라면 큐에 추가하면 방문 표시를 한다.

코드

       public int solution(int[,] maps)
        {
            int h;
            int v;

            int answer = 0;
            h = maps.GetLength(0);
            v = maps.GetLength(1);

            bool isEnd = false; 
            
            Queue<Tuple<int,int,int>> _queue = new Queue<Tuple<int, int, int>>();



            _queue.Enqueue(new Tuple<int, int, int>(0, 0, 1));
            
            // 방문 표시를 위한 맵 2차원 배열 
            bool[,] bools = new bool[h,v];


            // 델타 값
            int[] dx = new int[] { -1, 0, 1, 0 };
            int[] dy = new int[] { 0, 1, 0, -1 };

            while(_queue.Count > 0)
            {
                var current = _queue.Dequeue();     // 현재 위치
                int x = current.Item1;
                int y = current.Item2;
                int dis = current.Item3;

                if(x == h - 1 && y == v - 1)
                {
                    isEnd= true;
                    answer = dis;
                    return answer;
                }

                for (int i = 0; i < 4; i++)
                {
                    int newX = x + dx[i];
                    int newY = y + dy[i];


                    if(newX >= 0 && newY >= 0 && newX < h && newY < v && !bools[newX,newY] && maps[newX,newY] == 1 )
                    {
                        _queue.Enqueue(new Tuple<int, int, int>(newX, newY, dis + 1));
                        bools[newX,newY] = true;
                        answer = dis + 1;
                    }
                    
                }
            }

            if (!isEnd) return -1;
            
            return answer;
        }
    }

여기서 처음에 이동 가능 지점을 체크하는 if 문 안에 break 문을 작성해서 잘못된 값이 발생했었다.
break 문을 작성하지 않는 이유는 도착점에 도착했을 때 해당 경로가 최단 경로임을 보장하기 위해서다.
break가 존재한 경우 첫번째로 발견된 도착점까지의 경로를 반환하고 BFS 탐색을 종료하게 한다.