[BOJ][C#] 2589 보물섬

📕 문제

📌 링크

📗 접근 방식

이차원 배열(arr)을 탐색을 할 때, 땅('L')이라면 BFS탐색을 시작한다.
아래 조건을 만족한다면 Queue에 넣고 BFS 탐색을 계속 진행한다.

조건
1. 이동할 곳이 배열 범위를 벗어나지 않는다.
2. 이동할 곳이 물('W')이 아니다.
3. 방문한 적이 없던 곳이다.

처음에 1로 저장하여 BFS 탐색을 시작하기 때문에 1을 빼준 값을 리턴해준다.

BFS탐색하면서 나온 결과값을 계속 최대값으로 최신화 시켜준 후
모든 BFS 탐색이 끝날때 저장한 최대값을 출력시키도록 구현하였다.

📘 코드

namespace BOJ
{
    class No_2589
    {
        const int MAX = 52;

        static int r, c;
        static char[,] arr = new char[MAX, MAX];

        static void Main()
        {
            Input();
            Solution();
        }

        static void Input()
        {
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            r = inputs[0];
            c = inputs[1];

            for(int i = 0 ; i < r ; i++)
            {
                char[] charArray = Console.ReadLine().ToCharArray();

                for(int j = 0 ; j < c ; j++)
                    arr[i, j] = charArray[j];
            }
        }

        static void Solution()
        {
            int answer = 0;

            for(int i=0 ;i<r ;i++)
            {
                for(int j=0 ;j<c ;j++)
                {
                    if(arr[i, j] == 'L')
                    {
                        answer = Math.Max(answer, BFS(i, j));
                    }
                }
            }

            Console.Write(answer);
        }

        static int BFS(int startX, int startY)
        {
            int ret = 0;

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

            Queue<(int, int)> q = new Queue<(int, int)>();
            int[,] dist = new int[MAX, MAX];

            q.Enqueue((startX, startY));
            dist[startX, startY] = 1;

            while(q.Count > 0)
            {
                var cur = q.Dequeue();

                var curX = cur.Item1;
                var curY = cur.Item2;

                ret = Math.Max(ret, dist[curX, curY]);

                for(int dir=0 ;dir<4 ;dir++)
                {
                    var nx = curX + dx[dir];
                    var ny = curY + dy[dir];

                    if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                    if(arr[nx, ny] == 'W') continue;
                    if(dist[nx, ny] > 0) continue;

                    dist[nx, ny] = dist[curX, curY] + 1;
                    q.Enqueue((nx, ny));
                }
            }

            return ret - 1;
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색