[BOJ][C#] 3184 양

LimJaeJun·2023년 12월 23일

algorithm boj

PS/BOJ

목록 보기

72/108

📕 문제

📌 링크

📗 접근 방식

입력 받기:

행(R)과 열(C)의 크기 및 각 위치의 문자열('.', 'o', 'v', '#')을 입력받습니다.

방문 여부 체크 및 BFS:

각 위치를 순회하면서 방문한 적이 없고, 울타리('#')가 아닌 경우 BFS를 시작합니다.
BFS를 통해 현재 영역에 속한 양과 늑대의 수를 세고, 방문 여부를 체크합니다.

결과 계산:

각 영역을 BFS를 통해 탐색하면서 양과 늑대의 수를 세고, 해당 영역의 양 수와 늑대 수를 비교하여 전역적인 양과 늑대의 수를 누적합니다.

결과 출력:

모든 탐색이 끝난 후 최종적으로 양과 늑대의 수를 출력합니다.

일반적인 BFS 문제였던 것 같다.

📘 코드

namespace BOJ_3184
{
    class Program
    {
        static Queue<(int, int)> q = new Queue<(int, int)>();
        static int[] dx = { 1, 0, -1, 0 };
        static int[] dy = { 0, 1, 0, -1 };
        static int sheepCount = 0;
        static int wolfCount = 0;
        
        static void Main()
        {
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int R = inputs[0];
            int C = inputs[1];

            char[,] board = new char[R, C];

            for (int i = 0; i < R; i++)
            {
                string s = Console.ReadLine();
                for (int j = 0; j < C; j++)
                {
                    board[i, j] = s[j];
                }
            }
            
            bool[,] visited = new bool[R, C];
            
            for (int i = 0; i < R; i++)
            {
                for (int j = 0; j < C; j++)
                {
                    if(visited[i,j] == true) continue;
                    
                    BFS(i, j, board, visited);
                }
            }
            
            Console.Write($"{sheepCount} {wolfCount}");
        }

        static void BFS(int a, int b, char[,] board, bool[,] visited)
        {
            int sheep = 0;
            int wolf = 0;

            q.Enqueue((a, b));
            visited[a, b] = true;

            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                int x = cur.Item1;
                int y = cur.Item2;

                if (board[x, y] == 'v') wolf++;
                else if (board[x, y] == 'o') sheep++;

                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];

                    if (nx < 0 || ny < 0 || nx >= board.GetLength(0) || ny >= board.GetLength(1)) continue;
                    if (visited[nx, ny] == true) continue;
                    if (board[nx, ny] == '#') continue;

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

            if (wolf >= sheep) wolfCount += wolf;
            else sheepCount += sheep;
        }
    }
}