[BOJ][C#] 2636 치즈

LimJaeJun·2023년 8월 26일

algorithm boj

PS/BOJ

목록 보기

18/108

📕 문제

📌 링크

📗 접근 방식

이전 처럼 BFS 진입시 매번 큐와 방문처리 배열을 선언하는 방식이 아니라 초기화를 시켜주었다.
BFS 조건
범위 밖일 경우, 방문한 적이 있는 경우 : 다음 탐색으로 넘어감
인접한 칸이 0일 경우 : 계속 탐색
인접한 칸이 1일 경우(치즈의 겉면) : 카운팅, 0으로 바꿈

📘 코드

namespace BOJ
{
    class No_2636
    {
        const int MAX = 102;

        static int r, c;
        static int result, time;
        static int[] dx = new int[] { 1, 0, -1, 0 };
        static int[] dy = new int[] { 0, 1, 0, -1 };
        static int[,] board = new int[MAX, MAX];
        static bool[,] visited = new bool[MAX, MAX];
        static Queue<(int, int)> q = new Queue<(int, int)>();

        static void Main()
        {
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            r = inputs[0];
            c = inputs[1];

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

            while(true)
                if(BFS())
                    break;
        }

        static bool BFS()
        {
            // BFS 돌때 해당 좌표의 인접한 칸중에 0이 있으면 겉면
            // 해당 칸을 0으로 만들어 주고 카운트증가

            // 또 다시 BFS 진행 BFS 도는 횟수 증가

            // BFS돈 횟수와 카운트 출력

            q.Clear();
            for(int i = 0 ; i < visited.GetLength(0) ; i++)
                for(int j = 0 ; j < visited.GetLength(1) ; j++)
                    visited[i, j] = false;
            int cnt = 0;
            time++;

            q.Enqueue((0,0));
            visited[0,0] = true;
            board[0,0] = 0;

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

                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(visited[nx, ny]) continue;
                    // 
                    if(board[nx,ny] == 0)
                    {
                        q.Enqueue((nx, ny));
                    }

                    // 
                    else
                    {
                        board[nx, ny] = 0;
                        cnt++;
                    }

                    visited[nx, ny] = true;
                }
            }

            if (cnt == 0)
            {
                Console.WriteLine($"{--time}");
                Console.WriteLine(result);

                return true;
            }
            else
            {
                result = cnt;

                return false;
            }
        }
    }
}