[BOJ][C#] 1303 전쟁 - 전투

LimJaeJun·2023년 12월 18일

algorithm boj

PS/BOJ

목록 보기

70/108

📕 문제

📌 링크

📗 접근 방식

board의 모든 좌표 탐색
방문한 적이 없다면 해당 좌표에서 BFS 시작
BFS(해당 좌표)
- 해당 좌표 방문 처리
- 좌표가 board를 벗어난 경우 continue
- board배열의 해당 좌표의 값과 같지 않으면 탐색 continue
- 이미 방문 처리된 좌표라면 continue
- 위 조건을 피한다면 방문 처리가 안되고 해당 좌표의 값과 현재 탐색 중인 좌표의 값이 같으므로 카운팅
- 카운팅된 값을 제곱하여 리턴
board의 해당 좌표
- B라면 black에 BFS 리턴값을 추가
- 'W'라면 white에 BFS 리턴값을 추가
white와 black을 출력

📘 코드

namespace BOJ_1303
{
    class Program
    {
        static void Main()
        {
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int m = inputs[0];
            int n = inputs[1];

            char[,] board = new char[n, m];
            
            int white = 0;
            int black = 0;

            for (int i = 0; i < n; i++)
            {
                string s = Console.ReadLine();
                for (int j = 0; j < m; j++)
                {
                    board[i, j] = s[j];
                }
            }
            
            bool[,] visited = new bool[n, m];
            
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (visited[i, j] != false) continue;
                    
                    if (board[i, j] == 'B')
                    {
                        black += BFS(i, j, board, visited);
                    }
                    else
                    {
                        white += BFS(i, j, board, visited);
                    }
                }
            }
            
            Console.WriteLine($"{white} {black}");
        }

        static int BFS(int a, int b, char[,] board, bool[,] visited)
        {
            int count = 1;
            
            Queue<(int, int)> q = new Queue<(int, int)>();
            int[] dx = { 1, 0, -1, 0 };
            int[] dy = { 0, 1, 0, -1 };

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

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

                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 (board[x, y] != board[nx, ny]) continue;
                    if (visited[nx, ny] == true) continue;

                    count++;

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

            return (int)Math.Pow(count, 2);
        }
    }
}