[BOJ][C#] 4963 섬의 개수

LimJaeJun·2023년 8월 30일

PS/BOJ

목록 보기

22/108

📕 문제

📗 접근 방식

BFS 방식으로 접근하였다.
첫 좌표부터 마지막 좌표까지 방문한 적이 없는 섬일 경우 BFS 탐색을 시작하며 탐색을 시작할 때마다 카운팅을 해준다. 모든 좌표를 탐색하였다면 카운팅한 수를 출력하고 사용한 데이터들을 모두 초기화시켜주었다.

BFS 진입 조건
1. (x,y)좌표에 방문한 적이 없고 섬(값이 1)인 경우

Queue 에 Enqueue하는 조건
1. 해당 좌표가 격자 크기를 벗어나지 않는 경우
2. 방문한 적이 없는 경우
3. 섬일 경우

📘 코드

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

        static int n, m, answer = 0;
        static int[,] board = new int[MAX, MAX];
        static bool[,] visited = new bool[MAX, MAX];
        static int[] dx = new int[] { 1, 0, -1, 0, 1, 1, -1, -1 };
        static int[] dy = new int[] { 0, 1, 0, -1, 1, -1, 1, -1 };
        static Queue<(int, int)> q = new Queue<(int, int)>();

        static void Main()
        {
            while(true)
            {
                int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                m = inputs[0];
                n = inputs[1];

                if(n == 0 && m == 0) break;

                for(int i=0 ;i<n ;i++)
                {
                    inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                    for(int j=0 ;j<m ;j++)
                    {
                        board[i, j] = inputs[j];
                    }
                }

                for(int i = 0 ; i < n ; i++)
                {
                    for(int j = 0 ; j < m ; j++)
                    {
                        if(board[i,j] == 1 && !visited[i, j])
                        {
                            BFS(i, j);
                            answer++;
                        }
                    }
                }

                Console.WriteLine(answer);

                ClearAll();
            }
        }

        static void ClearAll()
        {
            answer = 0;
            q.Clear();
            for(int i = 0 ; i < n ; i++)
                for(int j = 0 ; j < m ; j++)
                    visited[i, j] = false;
        }

        static void BFS(int x, int y)
        {
            q.Enqueue((x, y));
            visited[x, y] = true;

            while(q.Count > 0)
            {
                var cur = q.Dequeue();
                var curX = cur.Item1;
                var curY = cur.Item2;

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

                    if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if(board[nx, ny] == 0 || visited[nx, ny]) continue;

                    q.Enqueue((nx, ny));
                    visited[nx,ny] = true;
                }
            }
        }
    }
}